L. Lemper Cooking Competition(前缀和/逆序对/树状数组/归并排序)

题目 参考

题意

给定一个长度为n的整数数组a。每次可以做如下操作。

• 选择下标i, 1 < i < n
• 令a[i-1] += a[i];a[i+1] += a[i]; a[i] = -a[i]。

问最少需要多少次操作，才能使数组a所有元素都非负。如果不能做到，则输出-1。

思路

a[i] = -a[i]，实际上等价于a[i] -= 2*a[i]。 令pre[i] = a[1] + a[2] + … + a[i]。

如果我们操作了下标x，那么对于i = x + 1，pre的值也不受影响。 而pre[x-1] +=a[x]，pre[x] -= a[x]。 等价于pre[x], pre[x-1] = pre[x-1], pre[x]。

所以，每次操作，等价于选择下标1