转化成差分之后，差分数组里面正数的和一定不会小于负数的和的绝对值（因为\(h_i>0\)），所以答案的下界是正数的和
我们来证明一定存在一种方案达到下界
用数学归纳法。设差分数组为\(d\)
显然\(d_1≥0\)；也有\(d_1+d_2≥0\)（假设\(d_2\)为负），也就是说，我们可以通过先操作\(d_1\)和\(d_2\)来让\(d_2\)达到目标值的情况下，我们还可以操作\(d_1\)（当然也许刚好也不能操作了）
然后对于\(d_3\)，如果\(d_3\)的目标值为正，我们就不管，否则的话由于\(d_1+d_2+d_3≥0\)，我们可以继续操作\(d_1\)和\(d_3\)，且在\(d_3\)达到目标值之前都可以操作
所以最终一定存在一种合法的方案
标签：积木,大赛,差分,下界,目标值,操作,正数 From： https://www.cnblogs.com/dingxingdi/p/18134547