CF1775E The Human Equation 好题如何成为？

给出一个数组，可以挑选一个子数组，使得 \[奇数位置+1，偶数位置-1 \] 或者 \[偶数位置+1，奇数位置-1 \] 最少多少次，使得数组为0； 解法1： 观察发现，可以每次选取一个正 负 正……的序列，感性判断，每次选择最长的那个序列进行操作是最好的 于是可以选最长子序列进行操作 但是问题是，每次选取最长子序列时间复杂度太高 是否可以简化？ 观察发现，最长子序列的第一个，一定是第一个非0数字 可以计算，将这个非0数字变成0，需要多少次？ 如果它是正数，那么它前面的负数，是可以把它的值直接变小，并且它可以把后面的负数直接变大 如果它是负数， 则和正数一样 参考洛谷题解，开两个变量ps，ng ps代表剩余的 可以对正数操作的次数，假设ps为10，就像是这个数字前面有-10的负数一样 ng代表剩余的 可以对负数操作的次数 对于每一个数x 如果它是正数，则\(ps = max(ps-x,0),ng += x\) 如果它是负数，则\(ng = max(ps+x,0),ps -= x\) 最后的答案就是，ps+ng，即对前面负数的操作次数+对前面的正数的操作次数 解法2 观察操作，可以挑选一个子数组，使得 \[奇数位置+1，偶数位置-1 \] 或者 \[偶数位置+1，奇数位置-1 \] 每次操作，可以使得所有数字之和+1，或者-1. 前缀和发现，对于前缀和数组，你可以对任意位置的数字+1或者-1 答案即前缀和数组pre 最大的正数-最小的负数