Submission #502103

#	Time	Username	Problem	Language	Result	Execution time	Memory
502103		chenwz	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	53 ms	720 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;  // 第几天剩余个任务
};

bool check(const int x) {
  queue<Task> Q;
  for (int d = 1, m; d <= N; d++) {      // m: 机器数
    for (m = x; !Q.empty() && m > 0;) {  // 处理遗留任务
      Task& t = Q.front();
      if (t.day + D < d) return false;  // 来不及了
      int c = min(t.cnt, m);
      m -= c, t.cnt -= c;
      if (t.cnt == 0) Q.pop();
    }
    if (!Q.empty() && Q.front().day + D < d)  // 有任务要过期
      return false;
    if (m < T[d]) Q.push({d, T[d] - m});  // 机器不够，延期
  }
  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 3.43s 32.17MB 1.31KB C++11

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:35:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   cout << ans << endl;
      |           ^~~

• Subtask 1: 0 / 100