제출 #726458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726458		jnjwnwnw	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1085 ms	65536 KiB

jobs

import java.util.*;
import java.io.*;
public class jobs {
    private class Pair{
        int ind, v;
        public Pair(int index, int val){
            this.ind = index;
            this.v = val;
        }
    }
    
    
    private int n, d, m;
    private int[][] arr;

    public static void main(String[] args) throws IOException{
        new jobs();
    }

    public jobs() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer sc = new StringTokenizer(br.readLine());
        n = Integer.parseInt(sc.nextToken());
        d = Integer.parseInt(sc.nextToken());
        m = Integer.parseInt(sc.nextToken());
        arr = new int[m][2];
        sc = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) { arr[i] = new int[]{i, Integer.parseInt(sc.nextToken())};}
        br.close();
        Arrays.sort(arr, (a, b) -> a[1]-b[1]);

        int lb = 0, ub = m, mid;
        while (lb < ub){
            mid = (lb+ub)/2;
            if (works(mid)){ub = mid;}
            else{lb = mid+1;}
        }

        System.out.println(lb);
        int j = 0;
        for(int i = 0; i < n; i++){
            int end = Math.min(m, j + lb);
            for(; j < end; j++){
                if (arr[j][1] > i+1){break;}
                System.out.print(arr[j][0] + 1 + " ");
            }
            System.out.println(0);
        }
    }

    public boolean works(int numMachines){
        int done = 0;
        for(int days = 1; days<=(n-d); days++){
            int end = Math.min(m, done+numMachines);
            for (;done<end;done++){
                if (arr[done][1] > days){
                    break;
                }
            }
        } return (done==m);
    }
}

• Subtask 1: 0 / 100