UVa 1614 - Hell on the Markets

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

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

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

Sample Input

1
2
3
4
4
1 2 3 3
4
1 2 3 4

Sample Output

1
2
3
No
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],根據遞歸是可以證明的。只要總和是偶數,必然可以劃分成總和相同的兩堆。排序一下,從大的數字開始挑,貪心去完成目標的總和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
}