Submission #502102

#TimeUsernameProblemLanguageResultExecution timeMemory
502102chenwzJob Scheduling (CEOI12_jobs)C++11
0 / 100
58 ms1596 KiB
// CEOI2012 - Job Scheduling #include <bits/stdc++.h> using namespace std; int N, D, M; vector<int> T; // T[d]: 第d天的任务个数 struct Task { int day, cnt; // 第d天的cnt个任务 }; bool check(const int K) { queue<Task> Q; for (int d = 1, k; d <= N; d++) { // k: 机器数 for (k = K; !Q.empty() && k > 0;) { // 处理遗留任务 Task& t = Q.front(); if (t.day + D < d) return false; // 来不及了 int c = min(t.cnt, k); k -= c, t.cnt -= c; if (t.cnt == 0) Q.pop(); } if (!Q.empty() && Q.front().day + D < d) // 有任务要过期 return false; if (k < T[d]) Q.push({d, T[d] - k}); // 机器不够,延期 } return true; } int main() { ios::sync_with_stdio(false), cin.tie(0); cin >> N >> D >> M, T.resize(N + 1); for (int i = 1, d; i <= M; ++i) cin >> d, T[d]++; int L = 1, R = M, ans; while (L <= R) { //普通二分,最多M台机器 int m = (L + R) / 2; check(m) ? ans = m, R = m - 1 : L = m + 1; } cout << ans << endl; return 0; } // Accepted 100 [CEOI2012]工作规划 367ms 856.00KB 992B C++11

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:34:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |   cout << ans << endl;
      |           ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...