CF2130B Pathless

· · 题解

题目传送门

思路

我们设原数组 a 的各个数之和为 sum。

  1. 若 sum > s，因为每个数字都会被访问，所以数值和一定会超过 s，输出原数组即可。
  2. 若 sum = s，此时不管怎样排列数组，只要从 1 走到 n 就一定合法，此时输出 -1。
  3. 若 s - sum = 1，当原数组存在相邻的 0 和 1 就一定合法（折返），所以我们要避免出现相邻的 0 和 1，可以将 2 放在 0 和 1 之间，即先输出所有的 0，再输出所有的 2，最后输出所有的 1。
  4. 若 s - sum > 1，和上种情况类似，如果出现相邻的 0 和 1，就可以不停地折返 +1。所以还是要将 2 放在 0 和 1 之间。此时会出现相邻的 0 和 2，以及相邻的 2 和 1，其折返一次的贡献分别为 2 和 3，可以证明这两种贡献可以组成任意多的贡献。此时无解，输出 -1。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N=50+5;
int a[N];
void solve()
{
    int n,s;
    cin >>n>>s;
    int cnt0=0,cnt1=0,cnt2=0;
    long long sum=0; 
    for(int i=1;i<=n;i++)
    {
        cin >>a[i];
        sum+=a[i];
        if(a[i]==0) cnt0++;
        if(a[i]==1) cnt1++;
        if(a[i]==2) cnt2++;
    }
    if(sum>s)
    {
        for(int i=1;i<=n;i++) cout <<a[i]<<" ";
    }
    else if(sum==s || s-sum>1) cout <<-1;
    else
    {
        for(int i=1;i<=cnt0;i++) cout <<0<<" ";
        for(int i=1;i<=cnt2;i++) cout <<2<<" ";
        for(int i=1;i<=cnt1;i++) cout <<1<<" ";
    }
    cout <<'\n';
}
int main()
{
    int t;
    cin >>t;
    while(t--) solve(); 
    return 0;
}