题解 CF1427A 【Avoiding Zero】

这题巨降智。。

做法1：真按它说的随机打乱，1000次左右还没有解就认为无解。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=55;

int a[maxn],n;

bool check()
{
	int sum=0;
	for(int i=1;i<=n;++i)
	{
		sum+=a[i];
		if(sum==0) return 0;
	}
	puts("YES");
	for(int i=1;i<=n;++i)
		printf("%d ",a[i]);
	putchar('\n');
	return 1;
}

int main()
{
	int t,flag;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);flag=0;
		for(int i=1;i<=n;++i)
			scanf("%d",a+i);
		for(int i=1;i<=1000;++i)
		{
			random_shuffle(a+1,a+n+1);
			if(check()) {flag=1;break;}
		}
		if(!flag) puts("NO");
	}
	return 0;
}

不知道为啥没卡。。。

然而我们观察前缀和的性质，我们先求整个序列的和，如果大于0则说明正数多，就从大到小排一遍序，小于0则负数多，从小到大排序，这样可以保证每个前缀和均不为0。如果和为0则无解，直接输出NO。

然后就没有了。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=55;

int a[maxn],n,sum;

bool cmp(const int &x,const int &y)
{
    return x>y;
}

int main()
{
	int t,flag;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);flag=sum=0;
		for(int i=1;i<=n;++i)
			scanf("%d",a+i),sum+=a[i];
        if(sum==0) {puts("NO");continue;}
		if(sum>0) sort(a+1,a+n+1,cmp);
        else sort(a+1,a+n+1);
        puts("YES");
        for(int i=1;i<=n;++i)
            printf("%d ",a[i]);
        puts("");
	}
	return 0;
}