题解 P6470 【[COCI2008-2009#6]CUSKIJA】

Alex_Wei · 2020-04-25 15:52:21 · 题解

题面传送门。

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

一些约定：我们设

• 序列 x 为 a 中除三余 0 的数。
• 序列 y 为 a 中除三余 1 的数。
• 序列 z 为 a 中除三余 2 的数。

首先判断无解。

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