Untitled

mail@pastecode.io avatarunknown
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);
  }
}