Email Filing (USACO Silver 2022 February)
这是一道相对繁琐的模拟题。题目有 M 个文件夹，N 封邮件，屏幕上同时显示 K 个文件夹和 K 封邮件。问题是：能否把所有邮件都归档完成。
本题的第一个关键点在于，文件夹和邮件在移动过程中其实各自有不同的规律，其中文件夹的位置只能不断向后，不能回滚。实际上，我们可以计算出文件夹应该处于什么位置：就是“当前还有未归档邮件中，编号最小的文件夹 x”。此时屏幕显示的文件夹的左边界不能大于 x，否则有邮件无法归档；也不能小于 x，否则可能错过可归档的邮件，因此最优的文件夹区间就是 [x, x+k)（左闭右开区间）。
接下来，我们用双指针来模拟归档邮件的过程。代码中的 [l, r) 表示屏幕上显示的邮件编号区间，num 表示当前屏幕上的邮件数量，total 表示已归档邮件数量。归档过程采用贪心策略：每当屏幕上有能被归档的邮件时就立刻归档，这样最优。
第二个关键点，是要搞清楚归档过程中每一步的逻辑，并严格实现，保证过程的正确性。整体可以分为两个阶段：
- 向上滚动邮件阶段：此时邮件只能不断往上滚动，已经离开屏幕上边界的邮件此时不能回来；
- 当滚到最底后，如果屏幕上邮件被归档，导致数量少于 K，那些已经滚出屏幕的邮件有机会重新回到范围中，否则过程结束。
在实现模拟时还要注意两个细节：
- 当文件夹的边界移动时，屏幕上的部分邮件可能突然变得可以归档，需要去除
[l, r)区间里已归档的邮件。一个容易实现的做法是用gone[i]这种标记数组记录每封邮件的归档状态。 - 虽然看上去复杂度较高，因为尝试归档屏幕上邮件的过程可能在每次移动文件夹时都进行一次，严格来说复杂度是 ，但实际测试下来最慢耗时也不到 10ms，完全可接受。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, m, n, k;
int x; // 当前文件夹位置
int l,r; // 屏幕范围 [l,r]
int num; // 屏幕上的邮件数量
int total; // 已归档的邮件数量
int f[100005];
bool gone[100005];
int cnt[10005];
int main() {
scanf("%d", &t);
while (t--) {
memset(gone, 0, sizeof(gone));
memset(cnt, 0, sizeof(cnt));
scanf("%d %d %d", &m, &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &f[i]);
cnt[f[i]]++;
}
x = 1; l = 1; r = 1; total = 0; num = 0;
while (total < n) { // 直到所有邮件都被归档
int flag = 0;
while (cnt[x] == 0 && x < m)
x++, flag = 1; // 移动文件夹
if (flag || r > n) { // 尝试归档屏幕上的邮件
num = 0;
for (int i = l; i < r; i++) {
if (gone[i]) continue;
if (f[i] - x < k) {
gone[i] = true;
cnt[f[i]]--;
total++;
} else num++;
}
}
if (r <= n) { // 第一阶段：向上滚动邮件
while (num == k) { // 移动左边界
if (!gone[l]) num--;
l++;
}
while (num < k && r <= n) {// 移动右边界
if (f[r] - x < k) {
gone[r] = true;
cnt[f[r]]--;
total++;
} else num++;
r++;
}
} else { // 第二阶段：到底后回滚邮件
if (num == k || l == 1)
break; // 如果屏幕已满或已包含所有邮件，则结束
while (num < k && l > 1) {
l--;
if (!gone[l]) num++;
}
}
}
if (total == n) printf("YES\n");
else printf("NO\n");
}
return 0;
}