# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
424154 | 2021-06-11T17:22:55 Z | PikaChu999 | Job Scheduling (CEOI12_jobs) | Java 11 | 0 ms | 0 KB |
/* 8 2 12 1 2 4 2 1 3 5 6 2 3 6 4 */ import java.util.*; import java.io.*; public class Main { public static long numDays; public static long maxDelay; public static int numRequests; public static Request[] requests; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer details = new StringTokenizer(br.readLine()); numDays = Long.parseLong(details.nextToken()); maxDelay = Long.parseLong(details.nextToken()); numRequests = Integer.parseInt(details.nextToken()); requests = new Request[numRequests]; StringTokenizer r = new StringTokenizer(br.readLine()); for(int x = 0; x < numRequests; x++) requests[x] = new Request(x, Long.parseLong(r.nextToken())); Arrays.sort(requests); //System.out.println(Arrays.toString(requests)); //output is formatted by requests + " " + 0 long min = 0; long max = 10000000; while(min < max){ long mid = (min + max)/2; if(works(mid)){ max = mid; } else min = mid + 1; } generate(max); br.close(); } public static boolean works(long numMachines){ PriorityQueue<Request> delayed = new PriorityQueue<Request>(); long currentDay = 0; int requestInd = 0; long available = numMachines; while(currentDay <= numDays){ //System.out.println(currentDay + " " + delayed + " " + requestInd); //even on days where there are no new requests one can work on the delayed ones available = numMachines; while(!delayed.isEmpty() && available > 0){ available--; Request cur = delayed.poll(); if(currentDay - cur.day > maxDelay) return false; } while(requestInd < numRequests && requests[requestInd].day == currentDay){ if(available > 0){ available--; requestInd++; } else{ delayed.add(requests[requestInd]); requestInd++; } } currentDay++; } return requestInd >= numRequests - 1; } public static void generate(long numMachines){ System.out.println(numMachines); PriorityQueue<Request> delayed = new PriorityQueue<Request>(); long currentDay = 0; int requestInd = 0; long available = numMachines; while(currentDay <= numDays){ //System.out.println(currentDay + " " + delayed + " " + requestInd); //even on days where there are no new requests one can work on the delayed ones ArrayList<Request> processed = new ArrayList<Request>(); available = numMachines; while(!delayed.isEmpty() && available > 0){ available--; processed.add(delayed.poll()); } while(requestInd < numRequests && requests[requestInd].day == currentDay){ if(available > 0){ available--; processed.add(requests[requestInd]); requestInd++; } else{ delayed.add(requests[requestInd]); requestInd++; } } currentDay++; String ret = ""; for(Request r : processed) ret += r.toString() + " "; System.out.println(ret + "0"); } } } class Request implements Comparable<Request>{ long day; int id; public Request(int i, long d){ day = d; id = i; } public int compareTo(Request r){ if(r.day < day) return 1; else if(r.day > day) return -1; return id - r.id; } public String toString(){ return String.valueOf(id); } }