自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:21:05，当前版本为作者最后更新于2020-04-25 15:52:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面传送门。

题意简述：给定一个序列 $a$，求出是否有一种排列满足相邻两数之和不是 $3$ 的倍数。

一些约定：我们设

• 序列 $x$ 为 $a$ 中除三余 $0$ 的数。
• 序列 $y$ 为 $a$ 中除三余 $1$ 的数。
• 序列 $z$ 为 $a$ 中除三余 $2$ 的数。
• $|f|$ 表示序列 $f$ 的大小。

首先判断无解。

Case $1$：$|y|+|z|+1<|x|$。

有 $|y|+|z|+1$ 个 “空位” 可以放 $3$ 的倍数，根据抽屉原理，如果 $|x|>|y|+|z|+1$，则必然有两个 $3$ 的倍数放在同一个 “空位” 里，即相邻。故无解。

Case $2$：$|y|,|z|>0$ 且 $|x|=0$。

如果 $|y|,|z|>0$ 且 $|x|=0$，则必然会有一个除三余 $1$ 的数与除三余 $2$ 的数相邻。故无解。

接下来考虑构造。构造方法如下：

首先输出所有除三余 $1$ 的数。输出每个数前，如果 $|x|>1$，则先输出一个除三余 $0$ 的数 $x_1$，然后将其从 $x$ 中弹出（$x$ 的大小会减少，即 $|x|\gets|x|-1$）。

• 为什么是 $|x|>1$？因为除三余 $1$ 的数和除三余 $2$ 的数之间要有一个除三余 $0$ 的数隔开来。

接着输出所有除三余 $2$ 的数。输出每个数前，如果 $|x|>0$，则先输出一个除三余 $0$ 的数 $x_1$，然后将其从 $x$ 中弹出（$x$ 的大小会减少，即 $|x|\gets|x|-1$）。

最后可能还剩下一个除三余 $0$ 的数，输出即可。

vector <int> b[3];

#define x b[0].size()
#define y b[1].size()
#define z b[2].size()
#define work cout<<b[0].back()<<" ",b[0].pop_back()

int main(){
	int n=read(),a;
	for(int i=1;i<=n;i++)a=read(),b[a%3].pb(a);
	if(y+z+1<x||y&&z&&!x)puts("No"),exit(0);
	puts("Yes");
	for(auto i:b[1]){if(x>1)work; cout<<i<<" ";}
	for(auto i:b[2]){if(x)work; cout<<i<<" ";}
	if(x)work;
	return 0;
}