제출 #498622

#제출 시각아이디문제언어결과실행 시간메모리
498622sohomduttaJob Scheduling (CEOI12_jobs)Java
0 / 100
171 ms12448 KiB
import java.util.*;
class jobschedule {
    static int n, d, m;
    static int [] requests;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        d = sc.nextInt();
        m = sc.nextInt();
        requests = new int[m];
        for(int i = 0; i < m; i++){
            requests[i]=sc.nextInt();
        }
        Arrays.sort(requests);

        //System.out.println(Arrays.toString(requests));
        int left = 1;
        int right = m;
        while(left!=right){
            int mid = left + (right-left)/2;
            if(works(mid)){
                right=mid;
            }else{
                left=mid+1;
            }
        }

        System.out.println(left);
    }
    public static boolean works(int machines){
        int [] timeArray = new int[m];
        int time = 1;
        timeArray[0]=1;
        int currentMachines = machines-1;
        for(int i = 1; i < m; i++){
            if(requests[i]==requests[i-1]){
                if(currentMachines==0){
                    currentMachines=machines-1;
                    time++;
                    timeArray[i]=time;
                }else{
                    currentMachines--;
                    timeArray[i]=time;
                }
            }else{
                time=Math.max(time+1, requests[i]);
                timeArray[i]=time;
                currentMachines=machines-1;
            }
        }
        for(int i = 0; i < m; i++){
            if(timeArray[i]-requests[i]>d){
                return false;
            }
        }
        return true;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...