解題區/解題區 - UVa

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;
}