自动搬运

查看原文

来自洛谷，原作者为

	sprads meaningless

搬运于2025-08-24 22:36:45，当前版本为作者最后更新于2022-03-16 22:21:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

平凡的模拟题 + 一些贪心。

不建议看题解，建议自己先写一写，说不定就过了。

名称约定

$m$ 个文件夹，$n$ 封邮件，电脑屏幕只能显示 $K$ 封邮件和文件夹。

$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。

代码

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