ACM找出一串数字是否能被分成两部分使其中一部分全部为负数，加上另一部分可以为0

Description

Most financial institutions had become insolvent during financial crisis and went bankrupt or were bought by larger institutions, usually by banks. By the end of financial crisis of all the financial institutions only two banks still continue to operate. Financial markets had remained closed throughout the crisis and now regulators are gradually opening them. To prevent speculation and to gradually ramp up trading they will initially allow trading in only one financial instrument and the volume of trading will be limited to i<tex2html_verbatim_mark> contracts for i<tex2html_verbatim_mark> -th minute of market operation. Two banks had decided to cooperate with the government to kick-start the market operation. The boards of directors had agreed on trading volume for each minute of this first trading session. One bank will be buying a_i<tex2html_verbatim_mark> contracts ( 1

a_i

i<tex2html_verbatim_mark> ) during i<tex2html_verbatim_mark> -th minute ( 1

n<tex2html_verbatim_mark> ), while the other one will be selling. They do not really care whether to buy or to sell, and the outside observer will only see the volume a_i<tex2html_verbatim_mark> of contracts traded per minute. However, they do not want to take any extra risk and want to have no position in the contract by the end of the trading session. Thus, if we define b_i = 1<tex2html_verbatim_mark> when the first bank is buying and b_i = - 1<tex2html_verbatim_mark> when the second one is buying (and the first one is selling), then the requirement for the trading session is that $sum_{{i=1}}^{{n}}$ a_ib_i = 0<tex2html_verbatim_mark> . Your lucky team of three still works in the data center (due to the crisis, banks now share the data center and its personnel) and your task is to find such b_i<tex2html_verbatim_mark> or to report that this is impossible.

Input

The input file contains several test cases, each of them as described below. The first line of the input contains the single integer number n<tex2html_verbatim_mark>( 1

100 000<tex2html_verbatim_mark> ). The second line of the input contains n<tex2html_verbatim_mark> integer numbers -- a_i<tex2html_verbatim_mark> ( 1

a_i

i<tex2html_verbatim_mark> ).

Output

For each test case, the first line of the output must contain `` Yes'' if the trading session with specified volumes is possible and `` No'' otherwise. In the former option a second line must contain n<tex2html_verbatim_mark> numbers -- b_i<tex2html_verbatim_mark> .

Sample Input

Sample Output

No
Yes
1 -1 -1 1
解题思路：
这个题目的大意是，输入一串数字，判断这一串数字能不能被分成两部分，如果不能就输出No。如果可以分成两部分，就找出用怎样的方法划分使得其中一部分数字的总和乘以-1，加上另一部分的总和可以为0.并且要在这些数字输入时对应的地方输出他是要乘以-1还是1.首先我们来判断这一串数字的总和能不能被分成两部分（注意：如果输入的数字只有一个是不能被分成相等的两部分的）。我们需要定义一个结构体，结构体里面包含两个数据，一个数据就是我们输入的数字，另一个就是这个数字输入的位置就是他的下标。我们可以把这时我们输入的每一个数字都是乘以1的，就用一个数组b来标记一下。然后我们用一个for循环来找到是要使哪些数字乘以-1，就把它对应的下标位置标记为-1（注意：结构体中的第二个数据就是他的下标，用b数组来标记）最后的输出也要利用b数组的标记。
程序代码：

#include <iostream>
#include <algorithm>
using namespace std;
int b[100005];
long long c,s;
struct node 
{
    int x;
    int y;
}a[100005];
int fun(node a,node b)
{
    return a.x>b.x;
}
int main()
{
    int n;
    while(cin>>n)
    { 
        s=0,c=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i].x;
            a[i].y=i;//记录数据的位置
            b[i]=-1;//标记
            s=s+a[i].x;
        }
        if(s%2||n==1)//如果总和是奇数或这总共就只有一个数据，就不可以分成两部分
        {
            cout<<"No"<<endl;
        }
        else
        {
            sort(a,a+n,fun);
            for(int k=0;k<n;k++)
            {
                if(c+a[k].x<=s/2)
                {
                    c=c+a[k].x;
                    b[a[k].y]=1;//注意a[k].y中存放的就是数据的位置
                    if(c==s/2)//结束循环
                       break;
                }
            }

            cout<<"Yes"<<endl;
            for(int j=0;j<n-1;j++)
                cout<<b[j]<<" ";
            cout<<b[n-1]<<endl;
        }
    }
    return 0;
}