Survival Train
plain_text
2 months ago
6.9 kB
1
Indexable
Never
package SurvivalTrain; // Doãn Thanh Tùng import java.util.ArrayList; import java.util.List; import java.util.TreeSet; class UserSolution { // mảng lưu các phần tử đối tượng Passengers Passenger[] passengers; // mảng các TreeSet TreeSet<Passenger> sections[]; // mảng các List, mỗi jobs[i] là một List ID các hành khách List<Integer> jobs[]; // nghiên cứu kỹ phần khởi tạo này void init(int N, int M, int J, int mPoint[], int mJobID[]) { sections = new TreeSet[N / M]; jobs = new ArrayList[J]; // lưu id của các hành khách cùng job for (int i = 0; i < J; i++) jobs[i] = new ArrayList<>(); passengers = new Passenger[N]; for (int i = 0; i < N; i++) { if (sections[i / M] == null) // sắp xếp giảm dần theo điểm, tăng dần theo id sections[i / M] = new TreeSet<>( (a, b) -> a.point == b.point ? a.id - b.id : b.point - a.point); passengers[i] = new Passenger(i, mPoint[i], mJobID[i]); sections[i / M].add(passengers[i]); jobs[mJobID[i]].add(i); } } void destroy() { } // cập nhật điểm của passenger có mID // kéo theo cập nhật sections[] --> cần tìm sections mà mID thuộc về int update(int mID, int mPoint) { Passenger p = passengers[mID]; for (int i = 0; i < sections.length; i++) { if (sections[i].remove(p)) { p.point += mPoint; sections[i].add(p); break; } } return p.point; } int updateByJob(int mJobID, int mPoint) { int sum = 0; for (int i = 0; i < sections.length; i++) { for (int pID : jobs[mJobID]) { if (sections[i].remove(passengers[pID])) { passengers[pID].point += mPoint; sum += passengers[pID].point; sections[i].add(passengers[pID]); } } } return sum; } // section có kiểu dữ liệu treeSet đã đã được định nghĩa với comparator sắp xếp --> nên khi add dữ liệu sẽ tự động sắp xếp // --> cần một List lưu các đối tượng cần dịch chuyển // chưa đủ, List này còn cần chia mảng như section để biết những hành khách sẽ dịch chuyển vào section nào // mNum là số lượng min, max cần đảo chỗ ở mỗi section int move(int mNum) { int sum = 0; List<Passenger> moved[] = new ArrayList[sections.length - 1]; for (int i = 0; i <= sections.length - 2; i++) { moved[i] = new ArrayList<>(); // find and remove min from section 0 to length-2 // store in moved[], chưa thêm lại vào sections[] tương ứng luôn for (int j = 0; j < mNum; j++) { Passenger minScore = sections[i].pollLast(); // xóa nhỏ nhất moved[i].add(minScore); sum += minScore.point; } // find and remove max from section 1 to length-1 // readd max to sections before for (int j = 0; j < mNum; j++) { Passenger maxScore = sections[i + 1].pollFirst(); sections[i].add(maxScore); sum += maxScore.point; } } // readd min to sections after // moved.length = sections.length - 1 for (int i = 0; i < moved.length; i++) sections[i + 1].addAll(moved[i]); return sum; } class Passenger { int id, point, jobID; Passenger(int mID, int mPoint, int mJobID) { id = mID; point = mPoint; jobID = mJobID; } } } package SurvivalTrain; //cải tiến UserSolution1 bằng cách truy xuất section nhanh hơn thay vì dùng vòng for trong 2 phương thức update và updateByJob import java.util.ArrayList; import java.util.List; import java.util.TreeSet; class UserSolution2 { // mảng lưu các phần tử đối tượng Passengers Passenger[] passengers; // mảng các TreeSet TreeSet<Passenger> sections[]; // mảng các List, mỗi jobs[i] là một List ID các hành khách List<Integer> jobs[]; int numS; // nghiên cứu kỹ phần khởi tạo này void init(int N, int M, int J, int mPoint[], int mJobID[]) { numS = N / M; sections = new TreeSet[numS]; jobs = new ArrayList[J]; // lưu id của các hành khách cùng job for (int i = 0; i < J; i++) jobs[i] = new ArrayList<>(); passengers = new Passenger[N]; for (int i = 0; i < N; i++) { if (sections[i / M] == null) // sắp xếp giảm dần theo điểm, tăng dần theo id sections[i / M] = new TreeSet<>( (a, b) -> a.point == b.point ? a.id - b.id : b.point - a.point); passengers[i] = new Passenger(i, mPoint[i], mJobID[i], i / M); sections[i / M].add(passengers[i]); jobs[mJobID[i]].add(i); } } void destroy() { } // cập nhật điểm của passenger có mID // kéo theo cập nhật sections[] --> cần tìm sections mà mID thuộc về int update(int mID, int mPoint) { Passenger p = passengers[mID]; sections[p.sectionID].remove(p); p.point += mPoint; sections[p.sectionID].add(p); return p.point; } int updateByJob(int mJobID, int mPoint) { int sum = 0; for (int pID : jobs[mJobID]) { Passenger p = passengers[pID]; sections[p.sectionID].remove(p); p.point += mPoint; sum += p.point; sections[p.sectionID].add(p); } return sum; } // section có kiểu dữ liệu treeSet đã đã được định nghĩa với comparator sắp xếp --> nên khi add dữ liệu sẽ tự động sắp xếp // --> cần một List lưu các đối tượng cần dịch chuyển // chưa đủ, List này còn cần chia mảng như section để biết những hành khách sẽ dịch chuyển vào section nào // mNum là số lượng min, max cần đảo chỗ ở mỗi section int move(int mNum) { int sum = 0; List<Passenger> moved[] = new ArrayList[numS - 1]; for (int i = 0; i <= numS - 2; i++) { moved[i] = new ArrayList<>(); // find and remove min from section 0 to length-2 // store in moved[], chưa thêm lại vào sections[] tương ứng luôn for (int j = 0; j < mNum; j++) { Passenger minP = sections[i].pollLast(); // xóa nhỏ nhất minP.sectionID++; moved[i].add(minP); sum += minP.point; } // find and remove max from section 1 to length-1 // readd max to sections before for (int j = 0; j < mNum; j++) { Passenger maxP = sections[i + 1].pollFirst(); maxP.sectionID--; sections[i].add(maxP); sum += maxP.point; } } // readd min to sections after // moved.length = sections.length - 1 for (int i = 0; i < moved.length; i++) sections[i + 1].addAll(moved[i]); return sum; } class Passenger { int id, point, jobID, sectionID; Passenger(int mID, int mPoint, int mJobID, int mSectionID) { id = mID; point = mPoint; jobID = mJobID; sectionID = mSectionID; } } }