题解：P8188 [USACO22FEB] Email Filing S

· · 题解

思路

首先，我们感觉一把，就知道这是一道模拟题，有一点点贪心。

通过读题我们发现，由于鼠标滚轮只能向下滚动，当左侧的文件夹一栏向下滚动后，就一定无法再往超过屏幕上方的文件夹拖动邮件。

因此，为了让邮件归档，我们必须先把要归档到第一个文件夹的邮件归档到第一个文件夹，全部归档完之后再把文件夹一栏向下滚动，然后继续把要归档到第二个文件夹的邮件归档到第二个文件夹，以此类推。

我们发现，当我们往当前文件夹（屏幕最上方的文件夹）归档邮件时，顺便把能归档到其他文件夹的邮件归档到其他文件夹一定不劣。因为你肯定最后还是要归档这些邮件，而现在能归档的邮件到了后面就有可能归不了档。

因此，我们在往当前文件夹归档邮件时，顺便把能归档到其他文件夹的邮件归档到其他文件夹，直到前文件夹没有要归档的文件为止。然后继续下一个文件夹的归档。

当此文件夹还有邮件要归档，但是屏幕显示的部分又没有任何邮件可以归档到一些文件夹，并且 r 已经超过了 n（到了最底下）,那么邮件就不能全部归档。因为这种情况表示要归档的邮件在屏幕上方，而你又无法通过归档其他邮件来使这个邮件下来。

代码

#include<bits/stdc++.h>
using namespace std;
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int nm=1e5+10;
int t,n,m,k;
int num[10005],a[nm];
typedef pair<int,int> p;
bool vis[nm];
string solve(){
    cin>>m>>n>>k;
    for(int i=1;i<=m;i++) num[i]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        num[a[i]]++;
        vis[i]=0;
    }
    int l=1,r=k; //屏幕上显示的邮件
    for(int i=1;i<=m;i++){
        while(num[i]){
            int flag=0;
            for(int w=l;w<=r;w++){
                if(!vis[w]&&a[w]>=i&&a[w]<=i+k-1){
                    num[a[w]]--;
                    vis[w]=1;
                    flag=1; //还能归档
                    if(r!=n) r++;
                    //如果没到底，下面的邮件上来
                }
            }
            if(num[i]&&r>n&&!flag) return "NO";
            //如果还有邮件且到底了且不能归档，返回NO
            if(num[i]) r++;
            //如果还有邮件，继续往下滑
            l=min(r,n);
            int cnt=1;
            if(vis[n]) cnt=0;
            while(cnt<k){
                l--;
                if(!vis[l]) cnt++;
            }
            //重新定位l
        }
    }
    return "YES";
}
signed main(){
    st();
    cin>>t;
    while(t--) cout<<solve()<<'\n';
    return 0;
}