P8188 [USACO22FEB] Email Filing S 题解
sprads
·
·
题解
前言
平凡的模拟题 + 一些贪心。
不建议看题解，建议自己先写一写，说不定就过了。
名称约定
$i$ 表示第 $i$ 个文件夹，$j$ 表示第 $j$ 封邮件。
$\forall j\in [1,n]$，$f_j$ 表示 $j$ 应投入的文件夹。
目标将所有邮件投入对应的文件夹中。
### 分析
**两个性质：**
1. 某一个文件夹一旦翻出屏幕，就回不来了（~~你不能让其他文件夹消失，让它掉回来~~）。
2. 根据 1，我们发现，当屏幕显示 $i\sim i+K-1$ 时，**只有**当**所有** $f_j = i$ 的邮件都放进文件夹 $i$ 时，才能上翻，把文件夹 $i$ 踢出屏幕（只有这样才能完成目标）。
### 流程
1. 根据性质 2，我们直接枚举 $1\sim m$。为了方便判断，引入 $c_i$，表示还未放入且 $f_j=i$ 的邮件的数量。枚举 $i$ 就代表应将 $c_i$ 减为 $0$。
2. 注意到相比于 $i-1(i>1)$，屏幕多显示出了 $i+K-1$（也只多了这一个文件夹）。将**此时**在**屏幕中的** $f_j=i+K-1$ 的邮件放入 $i+K-1$。于是就需要用 `set` 维护屏幕，方便删除；用 $m$ 个 `queue` 维护每个文件夹**在屏幕中的**邮件。
3. 分两种情况考虑邮件：
- 屏幕下方还有邮件，把它翻上来：如果屏幕中有 $K$ 封邮件，就把其中的第一封翻上去（这里可以用一个栈维护被翻上去的邮件）。其次，若新加入的邮件 $j$ 满足 $f_j\in[i,i+K-1]$，直接让 $c_{f_j}$ 减 $1$ 即可，否则邮件就得进入屏幕。
- 屏幕下方没有邮件，已经滚上去的邮件掉回屏幕：从维护滚上去邮件的栈中取出栈顶，同上面类似处理。不同的是，当屏幕中已有 $K$ 封邮件时，就代表无法完成目标，输出 `NO`。
4. 如果成功枚举完 $1\sim m$，就代表可以完成任务，输出 `YES`。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100005,M = 10005;
set<int> sce;//维护屏幕的set
queue<int> q[M];//维护每个文件夹在屏幕中的邮件的queue
int T,n,m,K,f[N],c[N],top,st[N];//维护滚出屏幕邮件的栈
int rd(){
int x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
void init(){//多测注意初始化
top = 0;
sce.clear();
for(int i = 1;i <= m;i++)
while(!q[i].empty())q[i].pop();
memset(c,0,sizeof(c));
}
bool check(){
int j = 1,t;
set<int>::iterator it;
for(int i = 1;i <= m;i++){
t = i + K - 1;
if(t <= m){//处理新进入屏幕的文件夹
c[t] -= q[t].size();
while(!q[t].empty()){//处理f[j]=i+K-1的邮件
int x = q[t].front();
q[t].pop();
sce.erase(x);
}
}
while(c[i]){//目标把文件夹 i 废掉。处理掉文件夹 i，就可以暂停处理邮件，优先翻出新的文件夹
int x = j <= n ? j : st[top--];//两种情况
if(sce.size() == K){
if(j <= n){
it = sce.begin();//踢出屏幕最顶上的邮件，维护set和queue和栈
st[++top] = *it;
q[f[*it]].pop();
sce.erase(*it);
}
else return 0;//邮件的第二种情况，无解
}
if(f[x] <= t)
c[f[x]]--;
else{
sce.insert(x);//屏幕中加入新邮件
q[f[x]].push(x);
}
if(j <= n)j++;//往后一封邮件
}
}
return 1;
}
int main(){
T = rd();
while(T--){
m = rd(),n = rd(),K = rd();
init();
for(int i = 1;i <= n;i++)
f[i] = rd(),c[f[i]]++;
check() ? puts("YES") : puts("NO");
}
return 0;
}
```