uva 1614——UVA 1614 - Hell on the Markets

客官°小女子只卖身不卖艺 2022-08-09 14:56 154阅读 0赞

Description

[![Download as PDF][]][Download as PDF 1]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* contracts for  *i* -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 contracts (  1![$ \\le$][_le]*a*i![$ \\le$][_le]*i* ) during  *i* -th minute (  1![$ \\le$][_le]*i*![$ \\le$][_le]*n* ), 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 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 when the first bank is buying and  *b*i = - 1 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\}\}$][_sum_i_1_n]*a*i*b*i = 0 . 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 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* (  1![$ \\le$][_le]*n*![$ \\le$][_le]100 000 ). The second line of the input contains  *n* integer numbers --  *a*i (  1![$ \\le$][_le]*a*i![$ \\le$][_le]*i* ).

## [Output][Input]  ##

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* numbers --  *b*i .

## [Sample Input][Input]  ##

4
    1 2 3 3
    4
    1 2 3 4

## [Sample Output][Input]  ##

No
    Yes
    1 -1 -1 1

题意： 给定一个长度为n的序列a，满足1<=ai<=i(很关键的条件），要求确定每个数的正负号，使得最后的和为0.没有这样的策略则输出No。

思路：贪心。因为1<=ai<=i，那么很容易得到的一个结论就是当所有数的绝对值得和为奇数时，一定没有方法使最后的和为0.当为偶数时，一定会存在一种方法。那么选取的时候必定是正1为sum的一半，-1为sum的一半，在遍历时不断贪心找到为+1的那一半即可。

code： #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=100005;
    const int M=20005;
    const int mod=1000000007;
    const double esp=1e-4;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define fr(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int v[N],s[N];
    int main()
    {
    	int n;
    	while (~scanf("%d",&n)&&n)
    	{
    		ll sum=0;
    		fr(i,1,n) scanf("%d",&v[i]),sum+=v[i];
    		
    		if (sum&1) {puts("No");continue;}
    		ll p=0;
    		for (int i=n;i>0;i--)
    		{
    			if ((p+v[i])*2<=sum)p+=v[i],s[i]=1;  //所有的为+1的那一半
    			else s[i]=-1;
    		}
    		puts("Yes");
    		fr(i,1,n) printf("%d ",s[i]);
    		puts("");
    	}
    }

[Download as PDF]: http://uva.onlinejudge.org/components/com_onlinejudge/images/button_pdf.png
[Download as PDF 1]: http://uva.onlinejudge.org/external/16/1614.pdf
[_le]: /images/20220731/fad31d3cb27e4f07890220ee924c61d7.png
[_sum_i_1_n]: http://uva.onlinejudge.org/external/16/4378img2.png
[Input]: http://acm.hust.edu.cn/vjudge/