Submission #502102

#	Time	Username	Problem	Language	Result	Execution time	Memory
502102		chenwz	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	58 ms	1596 KiB

jobs

// 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;
      |           ^~~

• Subtask 1: 0 / 100