自动搬运

查看原文

来自洛谷，原作者为

	_hxh 人生没有ctrl+z

搬运于2025-08-24 23:00:53，当前版本为作者最后更新于2024-07-17 15:21:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

分析

题意还是非常清楚的，为了帮助理解，我们把样例中依次启动的机器输出的序列和合法的启动方案放在一起看。（${\color{red} 第一台机器}，{\color{green} 第二台机器}，{\color{blue} 第三台机器}$）

$${\color{red} 1} {\color{green} 1} {\color{green} 2} {\color{red} 3} {\color{green} 3} {\color{red} 2} {\color{blue} 1} {\color{blue} 2} {\color{blue} 3} $$

因为每个数都出现了 $k$ 次，所以正好于 $k$ 台机器匹配。注意到题目中说“输出一种合法的启动方案”就可以，所以我们可以调整一下：

$${\color{red} 1} {\color{green} 1} {\color{red} 2} {\color{red} 3} {\color{green} 3} {\color{green} 2} {\color{blue} 1} {\color{blue} 2} {\color{blue} 3} $$

我们可以让该数字第 $j$ 次出现被第 $j$ 台机器打印，这样可以直接用一个数组记录。设 $pos_{i,j}$ 为数字 $i$ 第 $j$ 次出现的位置，那么 $pos_{1,1} < pos_{1,2} < \dots < pos_{1,k},pos_{2,1} < pos_{2,2} < \dots < pos_{2,k}\dots$ 一定成立。而输入的依次启动的机器输出的序列一定是合法的，这样 $pos_{1,j},pos_{2,j},\dots,pos_{n,j}$ 位置上的数字就可以匹配到第 $j$ 台机器上啦。

为什么 $m$ 对 $(a_i,b_i)$ 没有用呢？因为依次启动的机器输出的序列一定是合法的，即一定满足每个存储的 $a_i$ 都在 $b_i$ 前面，不需要开数组进行存储。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5; 
int n,k,m,a,b,x,nk[N];
int main()
{
	cin >> n >> k >> m;
	for (int i = 1;i <= m;i++)
		cin >> a >> b;
	for (long long i = 1;i <= n * k;i++)
	{
		cin >> x;
		cout << ++nk[x] << " ";
	}
	return 0;
}