Submission #461358

#	Time	Username	Problem	Language	Result	Execution time	Memory
461358		ryankim0709	Job Scheduling (CEOI12_jobs)	Java	0 / 100	1087 ms	65540 KiB

jobs

import java.util.*;
import java.io.*;

/* Test case simulation:
 * 8 2 12
 * 1 2 4 2 1 3 5 6 2 3 6 4
 * ----------------------- Sort Array
 * 1 1 2 2 2 3 3 4 4 5 6 6
 * ----------------------- Binary through possible min machines
 * 
 */
public class jobs {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int days = Integer.parseInt(st.nextToken());
		int maxDelay = Integer.parseInt(st.nextToken());
		int reqs = Integer.parseInt(st.nextToken());
		
		int[] requests = new int[reqs];
		int[] sortReqs = new int[reqs];
		HashMap<Integer,Integer> pos = new HashMap<>();
		
		st = new StringTokenizer(br.readLine());
		for(int x = 0; x < reqs; x++) {
			requests[x] = Integer.parseInt(st.nextToken());
			sortReqs[x] = requests[x];
			pos.put(x + 1, requests[x]);
		}
		Arrays.sort(sortReqs);
		
		int min = 1;
		int max = reqs;
		int mid;
		
		while(min < max) {
			mid = min + (max - min)/2;
			
			if(doesWork(sortReqs, maxDelay, mid, days)) {
				max = mid;
			}
			else {
				min = mid + 1;
			}
		}
		System.out.println(min);
	}
	
	public static boolean doesWork(int[] sortReqs, int maxDelay, int machines, int days) {
		int left = 0;
		int count = 0;
		for(int x = 0; x < days; x++) {
			for(int y = 0;  y < machines; y++) {
				if(sortReqs[left + y] - maxDelay > 0) {
					left = left + y - 1;
					break;
				}
				else {
					count ++;
				}
			}
		}
		if(count < sortReqs.length - 1) {
			return false;
		}
		return true;
	}
}

• Subtask 1: 0 / 100