The secret of being a bore is to tell everything

0%

[UVA1614] Hell on the Markets

题意

给你一个长度为$n(n\leq 10^5)$的序列$A$, 满足$1 \leq A_i \leq i$。求确定每个数的正负号,使得总和为$0$。

解题思路

如果不考虑那个诡异的条件,显然我们只需要求出序列$A$的子集和是否可以等于总和的一半即可。但是子集和问题(Subset Sum)是一个著名的NPC问题,显然无法在满足时间限制的条件下得到解。

于是我们必须考虑如何使用$1 \leq A_i \leq i$这个条件。我一开始的猜想就是如果序列总和$S_n$是偶数,那么在这个限制条件下一定存在一个子集$a$使得$Sum(a) = S / 2$。但是我无法证明它,也没法找到一个合适的贪心方法找出这个子集。

看了别人的题解才发现这个结论需要变得更强一点:对于前缀和$S_i$,以及$1$到$S_i$的每个整数$x$,一定能从前$i$个元素中找出一个子集使得子集的和等于$x$。证明可以使用归纳法:

$\textbf{Base Case: }$ 当$i = 1$的时候,我们有$a_1 = 1$,那么我们可以用$a_1$,凑出$S_1$。

$\textbf{Inductive Hypothesis: }$ 假设对于整数$k$,我们有对于所有$1$到$S_k$的整数,都存在一个由前$k$个数组成的集合,使得集合的和为这个整数。

那么对于整数$k+1$,新加入的这个$a_{k+1}$有$1 \leq a_{k+1} \leq k + 1$。此时$S_{k+1} = S_k + a_{k + 1}$。对于所有$x \leq S_k$,我们都可以用前$k$个元素组成。那么我们只需要考虑对于所有$S_k + 1 \leq x \leq S_k + k + 1$我们如何去组合就行了。假设我们有$a_{k+1} = y$,$S_{k + 1} = S_k + y$,那么$S_k + j (j \in [1, y])$可以由组成$S_k + j - y$的集合中,添加一个$a_{k+1}$组成。由于$y\geq j$,所以所有的$S_k + j - y$集合都可以由前$k$个元素组成,新加的元素只需要贡献$y$。因此我们有对于所有$1$到$S_{k+1}$的整数,都存在一个由前$k+1$个数组成的集合,使得集合的和为这个整数。

于是此结论得证,我们一定可以凑出来$S_n/2$。但是怎样去凑呢?还是要利用这个结论。假设我们想用前$k$个元素凑出$x$,则一定有$x<=S_k$,那么如果$0 \leq x-a_k \leq S_{k-1}$,则前$k-1$个元素一定能凑出$x-a_k$。由于$x\leq S_k$,所以一定满足$x-a_k \leq S_{k-1}$。如果出现$x-a_k$为负数的情况,那么一定有$x \leq S_{k-1}$,否则根据前缀和,无法出现负数。由于$x \leq S_k$一直保持,所以一定有$x\leq S_1=1$,所以$x$最后一定为$0$。

至此,我们得出了一个凑出子集和等于$S_n/2$的方法,从后往前选取$a_i$,如果$a_i$的选取会超出$S_n/2$,那么就不选,由于上面的证明,最后一定选取的元素和一定为$S_n/2$。至此,这道题终于被解决了,有两个结论和两个不显然的证明,实在是难想啊。

时间复杂度

$O(n)$

参考代码

1
2
int arr[MAXN];
3
ll pref[MAXN];
4
void solve() {
5
    for (int i = 1; i <= n; i++) {
6
        scanf("%d", &arr[i]);
7
        pref[i] = pref[i - 1] + arr[i];
8
    }
9
    if (pref[n] & 1) {
10
        printf("No\n");
11
        return;
12
    }
13
    ll st = pref[n] / 2;
14
    for (int i = n; i >= 1; i--) {
15
        if (st - arr[i] >= 0) {
16
            st -= arr[i];
17
            arr[i] *= -1;
18
        }
19
    }
20
    printf("Yes\n");
21
    for (int i = 1; i <= n; i++) {
22
        if (i != 1) printf(" ");
23
        printf("%d", arr[i] < 0 ? -1 : 1);
24
    }
25
    printf("\n");
26
}
27
int main() {
28
    while (~scanf("%d", &n)) {
29
        solve();
30
    }
31
    return 0;
32
}