제출 #498625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498625		sohomdutta	Job Scheduling (CEOI12_jobs)	Java	0 / 100	158 ms	12336 KiB

jobs

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);
        for(int i = 0; i < n; i++){
            System.out.println(5 + " " + 0);
        }
        System.exit(0);
    }
    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;
    }
}

• Subtask 1: 0 / 100