제출 #1120972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120972		classic	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	248 ms	23504 KiB

jobs

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int numDay, limitDelay, numRequest;
	std::cin >> numDay >> limitDelay >> numRequest;
	std::vector<int> dayStartRequest(numRequest);
	for (int &day : dayStartRequest) {
		std::cin >> day;
	}
	std::vector<int> order(numRequest);
	iota(order.begin(), order.end(), 0);
	sort(order.begin(), order.end(), [&](int indexLeft, int indexRight) {
		return dayStartRequest[indexLeft] > dayStartRequest[indexRight];
	});
	sort(dayStartRequest.begin(), dayStartRequest.end(), std::greater<int>());
	int low = 1, high = numRequest, needMachine = high;
	while (low <= high) {
		int middle = low + ((high - low + 1) >> 1);
		int maxDelay = 0, day = 1;
		for (int index = numRequest - 1; index >= 0; ) {
			int machine = 0;
			while (index >= 0 && day >= dayStartRequest[index] && machine < middle) {
				maxDelay = std::max(maxDelay, day - dayStartRequest[index]);
				index--;
				machine++;
			}
			day++;
		}
		if (maxDelay <= limitDelay) {
			needMachine = middle;
			high = middle - 1;
		} else {
			low = middle + 1;
		}
	}
	std::cout << needMachine << '\n';
	std::vector<std::vector<int>> schedule(numDay);
	int day = 1;
	for (int index = numRequest - 1; index >= 0; ) {
		int machine = 0;
		while (index >= 0 && day >= dayStartRequest[index] && machine < needMachine) {
			schedule[day - 1].emplace_back(order[index] + 1);
			index--;
			machine++;
		}
		day++;
	}
	for (int day = 0; day < numDay; day++) {
		for (const int &index : schedule[day]) {
			std::cout << index << ' ';
		}
		std::cout << 0 << '\n';
	}
	return 0;
}

• Subtask 1: 100 / 100