Submission #880482

#	Time	Username	Problem	Language	Result	Execution time	Memory
880482		vjudge1	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	644 ms	14608 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
const int NN = 1e6 + 10;
int D[NN], n, d, m;
bool check(int k){
	priority_queue<int, vector<int>, greater<int>> Q;//记录完成任务的截止时间
	_for(i, 1, m) if(Q.size() < k){
		Q.push(D[i] + 1);  //未用满k个机器，使用新的机器
		if(D[i] + 1 > D[i] + d) return 0;
	}else{// 用最早用完的机器来做这个任务
		int p = Q.top();
		Q.pop();
		int x = max(p + 1, D[i] + 1);
		Q.push(x);
		if (x > D[i] + d + 1) return 0;
	}
	return 1;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> d >> m;
	_for(i, 1, m) cin >> D[i];
	sort(D + 1, D + m + 1);
	int l = 0, r = 1e9, mid;
	while(l < r) check(mid = l + r >> 1) ? r = mid : l = mid + 1;
	cout << r;
	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:8:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    8 |  _for(i, 1, m) if(Q.size() < k){
      |                   ~~~~~~~~~^~~
jobs.cpp: In function 'int main()':
jobs.cpp:26:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |  while(l < r) check(mid = l + r >> 1) ? r = mid : l = mid + 1;
      |                           ~~^~~

• Subtask 1: 0 / 100