Submission #361436

#TimeUsernameProblemLanguageResultExecution timeMemory
361436AnythingWithJJob Scheduling (CEOI12_jobs)Java
0 / 100
1098 ms60696 KiB
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class jobs { // 7 mins planning static int N,D,M; static int [] requests; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(System.out); StringTokenizer s = new StringTokenizer(br.readLine()); N = Integer.parseInt(s.nextToken()); D = Integer.parseInt(s.nextToken()); M = Integer.parseInt(s.nextToken()); requests = new int [M]; s = new StringTokenizer(br.readLine()); for (int i = 0; i < M; i++) { requests[i] = Integer.parseInt(s.nextToken()); } Arrays.sort(requests); int a = 1, b = M; while (a != b) { int mid = (a+b)/2; if (works(mid)) b=mid; else a = mid+1; } out.println(b); out.close(); } static boolean works (int numMachines) { PriorityQueue<Integer> machines = new PriorityQueue<>(); for (int i = 0; i < numMachines; i++) machines.add(0); int maxD = 0; for (int i = 0; i < M; i++) { int currDay = requests[i]; int nextAvalMachineDay = machines.poll()+1; if (nextAvalMachineDay > currDay) { maxD = Math.max(maxD,nextAvalMachineDay-currDay); } machines.add(Math.max(nextAvalMachineDay,currDay)); } return maxD <= D; } }
#Verdict Execution timeMemoryGrader output
Fetching results...