题解：P8188 [USACO22FEB] Email Filing S

思路

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

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

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

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

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

当此文件夹还有邮件要归档，但是屏幕显示的部分又没有任何邮件可以归档到一些文件夹，并且

r

已经超过了

n

（到了最底下）,那么邮件就不能全部归档。因为这种情况表示要归档的邮件在屏幕上方，而你又无法通过归档其他邮件来使这个邮件下来。

代码

CPP

#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;
}

题解：P8188 [USACO22FEB] Email Filing S

文章操作

思路

代码

相关推荐

评论

题解：P8188 [USACO22FEB] Email Filing S