题解：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;
}