Codeforces Global Round 11 A. Avoiding Zero(思维构造)

地址：http://codeforces.com/contest/1427/problem/A

题意：

给出a[]，对其进行重排列，保证不存在

b1+b2+...+bk!=0，k=1,2,3....n

解析：

脑子秀逗了，这题差点没搞出来。

首先求一下数组和sum

1：sum==0

很明显，一定不行。

2：sum>0

先放正数，然后负数

sum既然>0，那么正数加起来，绝对值一定大于负数的绝对值的，所以加的过程中，不可能出现0。

0的话，只要不放第一位就行，随便。

3：sum<0

先放负数，然后正数。

sum<0，那么负数和绝对值一定大于正数，所以这种放的方式，加的过程中，也不可能出现0。

0的话，只要不放第一位就行，随便。

#include<bits/stdc++.h>
#include<cmath>
#include<map>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int n;
map<int,int>mp;
int a[maxn];
void solve(int sum)
{
    sort(a+1,a+1+n);
    if(sum>0)
    {
        for(int i=n;i>=1;i--)
        {
            if(a[i]==0)
                continue;
            cout<<a[i]<<" ";
        }    
        if(mp[0])
        {
            for(int i=1;i<=mp[0];i++)
                cout<<"0"<<" ";
        }
        cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i]==0)
                continue;
            cout<<a[i]<<" ";
        }    
        if(mp[0])
        {
            for(int i=1;i<=mp[0];i++)
                cout<<"0"<<" ";
        }
        cout<<endl;        
    }
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int sum=0;
        mp.clear();
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
            mp[a[i]]++;
        }
        if(sum==0)
            cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;
            solve(sum);
        }
    }
}