题解：P8188 [USACO22FEB] Email Filing S

· · 题解

思路

对于这道题，根据题目描述可以判断出这是一道模拟题。

首先我们注意到，文件夹和邮件是两栏，可以分别翻动。

文件夹是不可以往上翻的，而邮件可以，所以我们要先选定要填充的文件夹，当该文件夹填充满了，就可以处理下一个文件夹了。

定义一个指针窗口，指向邮件，如果在该窗口不能继续归档或更换处理文件夹了，就可以更新该指针窗口。

注意跳过已经归档的邮件。

代码详解

#include <bits/stdc++.h>
using namespace std;
#define int long long
int T;
const int MAXN=1e5+5;
int a[MAXN];
bool vis[MAXN];
int num[MAXN],con[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) {
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        memset(con,0,sizeof(con));
        int cnt=0;
        int st=0,ed=0,now=0;
        int m,n,k;

        cin>>m>>n>>k;
        if(k==n||k==m) {
            cout<<"YES"<<"\n";
            continue;
        }
    //这里在输入时记录每个文件夹应有的数量
        for(int i=1; i<=n; i++) cin>>a[i],num[a[i]]++;
        now=1,st=1,ed=k;
    //now记录处理的文件夹
    //st为窗口起点，ed为窗口终点
        while(cnt<n) {
            bool flag=0;
      //flag记录是否有操作
            for(int i=st; i<=ed; i++) {
                if(vis[i]) continue;
                if(a[i]>=now&&a[i]<=now+k-1) {
                    cnt++;
                    vis[i]=1;
                    con[a[i]]++;
                    flag=1;
                    if(ed<n){
                        do ed++;
                        while(vis[ed]);
                    }
                    else {
                        do st--;
                        while(vis[st]);
                    }
        //do-while去除已归档的邮件
                }
            }
            while(con[now]==num[now]) flag=1,now++;
            while(vis[st]) st++;
            while(vis[ed]) ed++;
      //更新指针窗口
            if(!flag) {
                if(ed<n) {
                    int right=ed;
                    while(st<=right) {
                        do st++;
                        while(vis[st]);
                        do ed++;
                        while(vis[ed]);
                    }
                }
                else break;
            }
        }
        if(cnt==n) cout<<"YES"<<"\n";
        else cout<<"NO"<<"\n";
    }
    return 0;
}

完结撒花。