原题链接 Link
思路分析
可以发现 \(n + m\) 天之后必然是循环的。所以考虑前 \(n + m\) 天。
首先第一天必然要雇佣 \(k\) 个人。然后一天一天往后扫，直到遇到一天不足 \(k\) 人。假设这一天只有 \(x\) 人。如果 \(x=0\)，那么先在前一天雇佣一个人拿钥匙，然后再在这一天雇佣 \(k-1\) 个人（为了使人数最少，显然雇佣越晚越好）。否则直接在这一天雇佣 \(k-x\) 人。
最后要考虑 \(n+m+1\) 天能否拿到钥匙。由于循环性，这一天的上班人数已经够了（第一天的 \(k\) 个人回来了），但如果从 \(m + 1\) 天开始都没有雇佣过员工，会出现没有钥匙的情况。要单独判断，再多雇佣一个人送钥匙
AC 代码
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
namespace io {...};
using namespace io;
const int maxn = 4e3 + 5;
int n, m, k;
int cnt[maxn];
vector<int> ans;
int main() {
read(n); read(m); read(k);
for (int i = 1; i <= n; i++) {
cnt[i] = k;
}
for (int i = 1; i <= k; i++) {
ans.emplace_back(1);
}
for (int i = n + 1; i <= n + m; i++) {
if (cnt[i] < k) {
if (cnt[i] == 0) {
for (int j = 1; j <= n; j++) cnt[i + j - 2]++;
ans.emplace_back(i - 1);
}
while (cnt[i] < k) {
for (int j = 1; j <= n; j++) cnt[i + j - 1]++;
ans.emplace_back(i);
}
}
}
if (!cnt[n + m + 1]) {
ans.emplace_back(n + m);
}
write(ans.size());
for (int x : ans) {
write(x, ' ');
}
return 0;
}
|