题目传送门

思路

我们设原数组

a

的各个数之和为

sum

。

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

AC Code

CPP

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

CF2130B Pathless

文章操作

题目传送门

思路

AC Code

相关推荐

评论

CF2130B Pathless