제출 #1119364

#제출 시각아이디문제언어결과실행 시간메모리
1119364hujoJob Scheduling (CEOI12_jobs)Java
5 / 100
1065 ms65536 KiB
    import java.io.*;
    import java.util.*;
     
    public class jobs{
        static int N; static int M;
        static List<Job> jobs;
        static PrintWriter pr;
        public static void main(String []args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            pr = new PrintWriter(new OutputStreamWriter(System.out));
            StringTokenizer st = new StringTokenizer(br.readLine());
     
            N = Integer.parseInt(st.nextToken()); int D = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
            jobs = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<=M; i++){
                int id = Integer.parseInt(st.nextToken());
                jobs.add(new Job(i, id, id+D));
            }
            jobs.sort((j1, j2)->Integer.compare(j1.end, j2.end));
            int minmachine=binsearchLeft(0, M);
            printRes(minmachine);
            pr.close();
        }
        static boolean isGood(int machines){
            Queue<Job> q= new LinkedList<Job>();
            for(Job j: jobs){
                q.offer(j);
            }
            for(int i=1; i<=N; i++){
                int nleft = machines;
                while(nleft>0 && q.peek()!=null){
                    Job top = q.peek();
                    if(top.start >i){
                        break;
                    }
                    else{
                        q.poll();
                        nleft--;
                    }
                }
            }
            if(q.isEmpty()){
                return true;
            }
            else{return false;}
        }
        static void printRes(int min){
          	pr.println(min);
            Queue<Job> q= new LinkedList<Job>();
            for(Job j: jobs){
                q.offer(j);
            }
            for(int i=1; i<=N; i++){
                int nleft = min;
                while(nleft>0 && q.peek()!=null){
                    Job top = q.peek();
                    if(top.start >i){
                        break;
                    }
                    else{
                        pr.print(top.id+" ");
                        q.poll();
                        nleft--;
                    }
                }
                pr.print(0);
                pr.println();
            }
        }
     
     
     
        static int binsearchLeft(int left, int right){
            if(left>right){
                return -1;
            }
            int mid = left + (right-left)/2;
            if(isGood(mid)){
                int res = binsearchLeft(left, mid-1);
                if(res==-1){return mid;}
                else{return res;}
            }
            else{
                return binsearchLeft(mid+1, right);
            }
        }
     
     
        static class Job{
            int id; int start; int end;
            public Job(int id, int start, int end){
                this.id = id; this.start = start; this.end=end;
            }
        }
    }
#Verdict Execution timeMemoryGrader output
Fetching results...