人菜就要认错
前25min过了 ABC, 1:20过了D, 还是模拟过的, 是真的sb
题目
题解
模拟的就不说了, 太丢人了
这题正解是差分的思想, 我们要注意到, 使得全为0
意味着差分数组全为零, 因为 a[0] = 0, 意味着差分数组全为零的时候, 整个序列也全为0了
我们再来看两个操作, 从 1~i, 全部-1, 也就是 --a[1], ++a[i + 1], 这步可以使得差分数组内的 负数 变成0, 同时减小 a[1], 将其变0
也就是 差分数组 所有的 负数的和 的绝对值 等于 a[1]
再看另一个操作, 就是 i~n, -1, --a[i], ++a[n + 1], 我们又不管 原数组 n + 1是啥, 但我们发现这操作把 差分数组的 所有 大于0 的数减小到 0
所以我们只要让 负数绝对值和 <= a[1], 其他的差分数组大于0的(包括a[1]) 我们都能将其变为0, 答案就有了
差分真的妙啊