闲话

最难的部分想出来了，最后一步没想出来。wtcl呜呜呜。

题目大意

给定 $n$ 个数 $a_1...a_n$，随后你可以进行若干次操作，每次操作步骤如下：

• 选出 $a$ 中一个子序列（可以不连续）。

• 把子序列中的奇数项减一，偶数项加一；或者奇数项加一，偶数项减一。

求把 $n$ 个数全部变成 $0$ 的最少操作次数。

$1\le n\le2\times10^5,-10^9\le a_i\le10^9$

思路

首先如果要最少次数，那么也就是要尽量少的选择子序列。同时可以发现，由于子序列可以不连续，所以将一个数变得更大是没有意义的。那么就转化成了如何尽量少的减少子序列的选择次数。

之后，如果我想让子序列的个数变少，那么就是要将它变得尽可能长，也就是一次可以带动更多的减。那么就是正负正负或者负正负正最长即可。

我们这样就做出了 $O(n^2)$ 的做法。我们考虑优化。由于每个数早晚都要消掉，那么我们不妨考虑扫一遍每一次要将 $a_i$ 变成 $0$。但是就要问了，如果这样找的话万一中间有一个数比 $a_i$ 小不就分裂了吗，之后奇偶就不确定了。但是我们如果要增加 $1$ 的话就必然要减少 $1$，所以有两个子序列，那么我们用前面增加 $1$ 的子序列排除掉 $i$ 在把第二个减少子序列后的后半除了 $i$ 的拼到一起就可以在奇偶性不变的情况下不会出现问题了。负数同理，所以 $0$ 就不会出现问题了，操作数也不用变。也可以去看 VinstaG173 大佬写的题解。

之后我们可以记录两个变量，$f,z$，为上一个的剩余操作数（贡献），要分负正因为是正负正负或者负正负正，所以要从前面的符号不同的地方更新。那么如果当前是正数，那么自然对负数可以要增加 $a_i$，因为负数可以减少正数所剩余的次数，而正数的剩余操作数要减少 $a_i$ 因为用了这么多。所以可以感觉到是反过来的感觉。之后注意正数最多减到 $0$。所以就是当前数是正数时 $z=\max(z-a_i,0),f=f+a_i$，当前数是负数时 $f=\max(f-a_i,0),z=z+a_i$。

之后自然答案就是负数的剩余次数和正数的剩余次数。

代码

#include <iostream>
using namespace std;
typedef long long ll;
ll t,n,a;
int main(){
    scanf("%lld",&t);
    while (t--){
        scanf("%lld",&n);
        ll z=0,f=0;
        for (int i = 1; i <=n ; ++i) {
            scanf("%lld",&a);
            if(a==0){
                continue;
            }else if(a>0){
                z= max(z-a,ll(0));
                f+=a;
            }else{
                a=-a;
                f=max(f-a,ll(0));
                z+=a;
            }
        }
        printf("%lld\n",z+f);
    }
    return 0;
}