Untitled

 avatar
Darin
plain_text
2 years ago
2.8 kB
4
Indexable
Phân tích đoạn code sau và logic của nó. Cho tôi lời giải tối ưu, ngắn gọn hơn.

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

class UserSolution {
	TreeSet<Passenger> sections[];
	Passenger passengers[];
	List<Integer> jobs[];

	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)
				sections[i / M] = new TreeSet<>(
						(a, b) -> a.point == b.point ? a.id - b.id : b.point
								- a.point); // sắp xếp giảm dần theo điểm và
											// tăng dần theo id
			passengers[i] = new Passenger(i, mPoint[i], mJobID[i]);
			sections[i / M].add(passengers[i]);
			jobs[mJobID[i]].add(i);
		}
	}

	void destroy() {
	}

	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 treeSey đã đã đượ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

	int move(int mNum) {
		int sum = 0;
		// lưu danh sách hành khách
		List<Passenger> temp[] = new ArrayList[sections.length - 1];
		for (int i = 0; i <= sections.length - 2; i++) {
			temp[i] = new ArrayList<>();
			// find and remove min from section 0 to length-2
			// store in temp[]
			for (int j = 0; j < mNum; j++) {
				Passenger smallest = sections[i].pollLast(); // do sắp xếp giảm
																// dần
				temp[i].add(smallest);
				sum += smallest.point;
			}
			// find and remove max from section 1 to length-1
			// readd max to sections before
			for (int j = 0; j < mNum; j++) {
				Passenger largest = sections[i + 1].pollFirst();
				sections[i].add(largest);
				sum += largest.point;
			}
		}
		// readd min to sections after
		for (int i = 0; i < temp.length; i++)
			sections[i + 1].addAll(temp[i]);
		return sum;
	}

	class Passenger {
		int id, point, jobID;

		Passenger(int mID, int mPoint, int mJobID) {
			id = mID;
			point = mPoint;
			jobID = mJobID;
		}
	}
}
Editor is loading...