首页 > itarticle > uva 1614 – hell on the markets

uva 1614 – hell on the markets

admin 11月 11, 2020 0

contents

Problem

金融交易，它們希望賣出、買進交易結束後的差為零。

意即將數字分兩堆的結果相同。

Sample Input

Sample Output

1
2
3

Yes
1 -1 -1 1

Solution

由於保證 0 < a[i] <= i，基於這一點，可以發現到只考慮一個數字 a[1] 時，必然可以湊出 1 - a[1]，當考慮第 i 大數字時，保證前 i - 1 個數字可以湊出 1 ~ (i-1)，加上第 i 個數字必然可以湊出 1 ~ (i-1)+a[i] (1, 2, 3, ..., i-1, a[i], 1+a[i], ..., i-1+a[i])。

而事實上，可以湊出所有的 1 ~ sum[i]，根據遞歸是可以證明的。只要總和是偶數，必然可以劃分成總和相同的兩堆。排序一下，從大的數字開始挑，貪心去完成目標的總和。

#include <stdio.h>
#include <algorithm>
using namespace std;
	
pair<int, int> A[100000];
int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		long long sum = 0;
		int ret[100000] = {};
		for (int i = 0; i < n; i++) {
			scanf("%d", &A[i].first);
			A[i].second = i;
			sum += A[i].first;
		} 
		if (sum%2) {
			puts("No");
		} else {
			puts("Yes");
			sum /= 2;
			sort(A, A+n);
			for (int i = n-1; i >= 0; i--) {
				if (sum >= A[i].first)
					sum -= A[i].first, ret[A[i].second] = 1;
				else
					ret[A[i].second] = -1;
			}
			for (int i = 0; i < n; i++)
				printf("%d%c", ret[i], i == n-1 ? 'n' : ' ');
		}
	}
	return 0;
}