题解：CF2130B Pathless
Technocy
·
·
题解
题意
# 思路
我们可以在输入时便记录 $\sum^n_{i=1}a_i$ 以及 $0$，$1$，$2$ 的个数，然后令 $op=s-\sum^n_{i=1}a_i$。当 $op=1$ 或 $op<0$ 时，我们就可以先输出完所有的 $0$，再输出完所有的 $2$，最后输出剩下的 $1$；否则直接输出 $-1$。
# 证明
已知 $op=s-\sum^n_{i=1}a_i$，令 $sum=\sum^m_{j=1}a_{i_j}$，那么这里我们分 $3$ 种情况进行讨论：
- $op<0$：说明哪怕我全程只走一次都会导致 $sum>s$，如果我还来回走显然 $op$ 会更小，因此在该情况下任意排列均正确。
- $op=1$：说明 $s=sum+1$，那么我全程只要有一个 $1$ 和 $0$ 相邻，来回走一下，就会使 $sum+1\to sum=s$，因此，我们就要让 $0$ 和 $1$ 分隔开，故先输出所有的 $0$，再输出所有的 $2$，最后输出所有的 $1$ 即可使得无论如何都满足 $sum\ne s$。
- $op=0$ 或 $op>1$：那么此时无论我怎么进行排列，总会有 $0$，$1$，$2$ 之间存在相邻，那么进而我就可以得到 $2$，$3$，$5$，然后就可以通过任意个 $2$，$3$，$5$ 的组合得到任意大于等于 $2$ 的数，显然就无解了，此时输出 $-1$ 即可。
综上所述，当 $op<0$ 或 $op=1$ 时，我们可以通过先输出所有的 $0$，再输出所有的 $2$，最后输出所有的 $1$ 即为正确答案，而当 $op=0$ 或 $op>1$ 时，直接输出 $-1$ 即可，证毕。
# Code
```cpp
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define N 1006
using namespace std;
int t,n,s,a[N],sum;
int mp[N];//mp记录0,1,2的个数
inline int read();
int main(){
t=read();
while(t--){
memset(mp,0,sizeof(mp));//多测不清空，亲人两行泪
sum=0;
n=read();s=read();
for(int i=1;i<=n;i++) a[i]=read(),mp[a[i]]++,sum+=a[i];
s-=sum;
if(s==1 || s<0){
for(int i=1;i<=mp[0];i++) cout<<0<<" ";
for(int i=1;i<=mp[2];i++) cout<<2<<" ";
for(int i=1;i<=mp[1];i++) cout<<1<<" ";
cout<<endl;
}else cout<<-1<<endl;
}
return 0;
}
inline int read(){
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-48;ch=getchar();}
return x*f;
}
```