Untitled
plain_text
17 days ago
7.7 kB
2
Indexable
Never
import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.Scanner; import java.awt.Point; public class universityzoning { // public static void main(String[] args) throws FileNotFoundException { // Scanner scanner = new Scanner(new File("input.txt")); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int row = scanner.nextInt(), col = scanner.nextInt(), numOfFac = scanner.nextInt(), numOfStudents = scanner.nextInt(), G = scanner.nextInt(); int[] studentCounter = new int[numOfFac]; // int[][][] zoneLocations = new int[numOfFac][][]; // // int[numOfFac][numOfZoneCells][x,y] ArrayList<ArrayList<Point>> zoneLocations = new ArrayList<>(); // int[numOfFac][numOfZoneCells][x,y] ArrayList<ArrayList<ArrayList<Long>>> uniStudents = new ArrayList<>(); for (int i = 0; i < numOfFac; i++) { int facultyNumCells = scanner.nextInt(); ArrayList<ArrayList<Long>> init = new ArrayList<>(); zoneLocations.add(new ArrayList<Point>()); uniStudents.add(init); // zoneLocations[i] = new int[facultyNumCells][2]; // (x, y) coords for (int j = 0; j < facultyNumCells; j++) { int currRow = scanner.nextInt() - 1, currCol = scanner.nextInt() - 1; // location of the faculty zone Point p = new Point(currCol, currRow); zoneLocations.get(i).add(p); } } // TODO sort the zoneLocations here Comparator<Point> pointComparator = (p1, p2) -> { if (p1.y != p2.y) { return Integer.compare(p1.y, p2.y); } else { return Integer.compare(p1.x, p2.x); } }; // TODO is this correct? for (ArrayList<Point> arrayList : zoneLocations) { Collections.sort(arrayList, pointComparator); } // TODO I need to change it such that I would make an array of students first // and then compare later. // this is so that I can sort out the students first and then search by index // after // Add the students into an array list for (int i = 0; i < numOfStudents; i++) { // -1 because there's no 0,0 coord but instead it starts at 1,1 long currStudRow = scanner.nextInt() - 1, currStudCol = scanner.nextInt() - 1, // location of the students studId = scanner.nextInt() - 1, studFaculty = scanner.nextInt() - 1; ArrayList<Long> x_y_studentId = new ArrayList<>(); x_y_studentId.add(currStudCol); x_y_studentId.add(currStudRow); x_y_studentId.add(studId); uniStudents.get((int) studFaculty).add(x_y_studentId); } // sort out the students by their index number Comparator<ArrayList<Long>> studentIdComparator = new Comparator<ArrayList<Long>>() { @Override public int compare(ArrayList<Long> student1, ArrayList<Long> student2) { Long studentId1 = student1.get(2); // Index 2 contains the studentId Long studentId2 = student2.get(2); // Index 2 contains the studentId return Long.compare(studentId1, studentId2); } }; // sort the students by studentId for (ArrayList<ArrayList<Long>> facultyStudents : uniStudents) { Collections.sort(facultyStudents, studentIdComparator); } // **** End of sorting studentId **** // Check which students are not in the right zone for (int i = 0; i < numOfFac; i++) { ArrayList<ArrayList<Long>> facultyStudents = uniStudents.get(i); // get the students belonging to this faculty ArrayList<Point> points = zoneLocations.get(i); // get the points under this faculty for (int j = 0; j < facultyStudents.size(); j++) { ArrayList<Long> student = facultyStudents.get(j); // this should be sorted according to their studentId // already // if student is found in the designated cell if (points.get(j).getX() == student.get(0) && points.get(j).getY() == student.get(1)) { // set coords to null to indicate that they are in the right zone student.set(0, null); student.set(1, null); studentCounter[i]++; // students in the right place } } } // Calculate the steps needed to move int nG = 0; // the number of faculties that met the requirements long[] facultyTotalSteps = new long[numOfFac]; // TODO now I need to know which faculty would get the job done faster... for (int i = 0; i < numOfFac; i++) { long stepCounter = 0; int T = scanner.nextInt(); // the number of students needed per faculty int numOfStudentsNeeded = T - studentCounter[i]; ArrayList<Long> arrySteps = new ArrayList<>(); ArrayList<ArrayList<Long>> facultyStudents = uniStudents.get(i); // students belonging to this faculty /* * // Comparator * Comparator<ArrayList<Integer>> studentIdComparator = new * Comparator<ArrayList<Integer>>() { * * @Override * public int compare(ArrayList<Integer> student1, ArrayList<Integer> student2) * { * // Assuming student ID is at index 2 in each inner ArrayList * Integer studentId1 = student1.get(2); * Integer studentId2 = student2.get(2); * * return studentId1.compareTo(studentId2); * } * }; * * // Sort the facultyStudents ArrayList using the custom comparator * Collections.sort(facultyStudents, studentIdComparator); * * int[] arrySteps = new int[students.size()]; */ // calculate distance if (numOfStudentsNeeded > 0) { for (int j = 0; j < facultyStudents.size(); j++) { // x coordinate is null if they are in the designated cell if (facultyStudents.get(j).get(0) == null) { continue; // this student is in the right place } ArrayList<Long> student = facultyStudents.get(j); // the j-th student that is in the wrong place ArrayList<Point> studentInfo = zoneLocations.get(i); Point point = studentInfo.get(j); // gets the j-th position in the sorted cells // the problem here right now, is that I dono the position of this student // in relation to the students in his faculty // calculate distance needed long x = (long) (student.get(0) - point.getX()); long y = (long) (student.get(1) - point.getY()); // arrySteps[j] = (int) Math.abs(x) + (int) Math.abs(y); arrySteps.add((long) (Math.abs(x) + Math.abs(y))); } Collections.sort(arrySteps); for (int j = 0; j < numOfStudentsNeeded; j++) { // System.out.println("This is for faculty " + i); // System.out.println("Nearer students walk: " + arrySteps.get(j)); stepCounter += arrySteps.get(j); } } else { // check if the faculty has no need for their students to move nG++; } facultyTotalSteps[i] = stepCounter; } Arrays.sort(facultyTotalSteps); long totalSteps = 0; int facultiesNeeded = G - nG; int counter = 0; for (int j = 0; j < numOfFac; j++) { if (counter == facultiesNeeded) { break; } if (facultyTotalSteps[j] == 0) { continue; } totalSteps += facultyTotalSteps[j]; counter++; } System.out.println(totalSteps); } }