Submission #361436

#TimeUsernameProblemLanguageResultExecution timeMemory
361436AnythingWithJJob Scheduling (CEOI12_jobs)Java
0 / 100
1098 ms60696 KiB
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class jobs {
    // 7 mins planning
    static int N,D,M;
    static int [] requests;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer s = new StringTokenizer(br.readLine());
        N = Integer.parseInt(s.nextToken());
        D = Integer.parseInt(s.nextToken());
        M = Integer.parseInt(s.nextToken());
        requests = new int [M];
        s = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            requests[i] = Integer.parseInt(s.nextToken());
        }
        Arrays.sort(requests);
        int a = 1, b = M;
        while (a != b) {
            int mid = (a+b)/2;
            if (works(mid)) b=mid;
            else a = mid+1;
        }
        out.println(b);
        out.close();
    }
    static boolean works (int numMachines) {
        PriorityQueue<Integer> machines = new PriorityQueue<>();
        for (int i = 0; i < numMachines; i++) machines.add(0);
        int maxD = 0;
        for (int i = 0; i < M; i++) {
            int currDay = requests[i];
            int nextAvalMachineDay = machines.poll()+1;
            if (nextAvalMachineDay > currDay) {
                maxD = Math.max(maxD,nextAvalMachineDay-currDay);
            }
            machines.add(Math.max(nextAvalMachineDay,currDay));
        }
        return maxD <= D;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...