Untitled

 avatar
Darin
plain_text
a year ago
3.9 kB
1
Indexable
Never
package SurvivalTrain;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

class UserSolution2 {

	ArrayList<PriorityQueue<Passenger>> arrQueue;
	// map id hành khách vào hành khách
	HashMap<Integer, Passenger> mapP;
	// map id job với id hành khách
	HashMap<Integer, ArrayList<Integer>> jobType;

	// numPassenger, numSection, numJob, number of passengers per section
	int numP, numS, numJ, numPS;

	void init(int N, int M, int J, int mPoint[], int mJobID[]) {
		numP = N;
		numS = N / M;
		numPS = M;
		numJ = J;
		mapP = new HashMap<Integer, Passenger>();
		jobType = new HashMap<Integer, ArrayList<Integer>>();
		arrQueue = new ArrayList<PriorityQueue<Passenger>>();

		Passenger P;
		for (int i = 0; i < N; i++) {
			// khởi tạo hành khách
			P = new Passenger(i, mJobID[i], mPoint[i]);
			mapP.put(i, P);
			for (int j = 0; j < numJ; j++) {
				ArrayList<Integer> pList;
				if (mJobID[i] == j) {
					if (jobType.get(j) == null) {
						pList = new ArrayList<Integer>();
						pList.add(i);
						jobType.put(mJobID[i], pList);

					} else {
						pList = jobType.get(j);
						pList.add(i);
					}
					// đã tìm thấy j khớp mJobID, break;
					break;
				}
			}

		}
		// các hành khách trong một Section được lưu theo Queue có trật tự
		// có nhiều Section --> có nhiều Queue
		PriorityQueue<Passenger> PQ;
		for (int i = 0; i < numS; i++) {
			PQ = new PriorityQueue<Passenger>(new minFirst());
			for (int j = i * M; j < (i + 1) * M; j++) {
				PQ.add(mapP.get(j));
			}
			// mỗi một Section là một Queue được lưu
			arrQueue.add(PQ);
		}
	}

	int update(int mID, int mPoint) {
		Passenger P;
		if (mapP.containsKey(mID)) {
			P = mapP.get(mID);
			P.point += mPoint;
		}
		return mapP.get(mID).point;
	}

	int updateByJob(int mJobID, int mPoint) {
		int sum = 0;
		ArrayList<Integer> pList;
		if (jobType.containsKey(mJobID)) {
			pList = jobType.get(mJobID);
			for (int i : pList) {
				mapP.get(i).point += mPoint;
				sum += mapP.get(i).point;
			}
		}
		return sum;
	}

	int move(int mNum) {
		int sum = 0;
		PriorityQueue<Passenger> PQ;
		Passenger[][] Pmax = new Passenger[numS - 1][mNum];
		Passenger[][] Pmin = new Passenger[numS - 1][mNum];
		for (int i = 0; i < numS - 1; i++) {
			PQ = new PriorityQueue<Passenger>(new minFirst());
			PQ.addAll(arrQueue.get(i));
			arrQueue.remove(i);
			arrQueue.add(i, PQ);
		}

		for (int i = 0; i < numS - 1; i++) {
			for (int k = 0; k < mNum; k++) {
				Pmin[i][k] = arrQueue.get(i).poll();
			}
		}
		for (int i = 1; i < numS; i++) {
			PQ = new PriorityQueue<Passenger>(new maxFirst());
			PQ.addAll(arrQueue.get(i));
			arrQueue.remove(i);
			arrQueue.add(i, PQ);
		}
		for (int i = 0; i < numS - 1; i++) {
			for (int k = 0; k < mNum; k++) {
				Pmax[i][k] = arrQueue.get(i + 1).poll();

			}
		}
		for (int i = 0; i < numS - 1; i++) {
			for (int k = 0; k < mNum; k++) {
				arrQueue.get(i).add(Pmax[i][k]);
				arrQueue.get(i + 1).add(Pmin[i][k]);
				sum = sum + Pmin[i][k].point + Pmax[i][k].point;
			}
		}
		return sum;
	}

	class Passenger {
		int id;
		int jId;
		int point;

		public Passenger(int pID, int jID, int pPoint) {
			id = pID;
			jId = jID;
			point = pPoint;
		}
	}

	class minFirst implements Comparator<Passenger> {
		public int compare(Passenger a, Passenger b) {
			if (a.point == b.point)
				return b.id - a.id;
			else
				return a.point - b.point;
		}

	}

	class maxFirst implements Comparator<Passenger> {
		public int compare(Passenger a, Passenger b) {
			if (a.point == b.point)
				return a.id - b.id;
			else
				return b.point - a.point;
		}
	}

	void destroy() {
	}
}