P2748 Landscaping P题解-526互联

P2748 Landscaping P
由于 \(a_i,b_i\) 很小，可以将每单位土单独考虑，这样就有若干单位需要得到处理的土。
但按照常规思维，从前往后依次考虑前 \(i\) 盆花盆的最优解，就有可能影响后面的决策（因为土既可以左移也可以右移），这时可以考虑 反悔贪心。
可以从一个例子得到启发：
假设现在有 \(3\) 盆 \(i,j,k(i<j<k)\)， \(i\) 少土，\(j\) 多土，\(k\) 少土，为了方便假设差都是 \(1\)。
只考虑 \(i\)，由于前面没有土，我们先花费 \(x\) 把 \(i\) 补齐。
到了 \(j\)，如果直接弃掉，代价为 \(y\)，如果选择向 \(i\) 移土，那么可以省掉之前花费 \(x\) 的代价，进行反悔，此时代价为 \((j-i)\times z-x\)，记 \(v=\min(y,(j-i)\times z-x)\)，那么处理 \(j\) 这里的土处理的代价为 \(v\)。
到了 \(z\)，如果直接移进来，代价为 \(x\)，如果选择把 \(j\) 的土移过来，反悔掉 \(j\) 时进行的操作，代价为 \((k-j)\times z-v\)。
我们发现：如果在 \(j\) 反悔掉 \(i\) 所进行的操作，设 \(v\) 为 \(i\) 操作的代价，则此次代价为 \((j-i)\times z-v=jz-(iz+v)\)，因此，如果我们想要代价最小，需要找使 \(iz+v\) 最大的 \(i\)，用大根堆维护，取出来后与 \(x(y)\) 进行对比，取小的那个作为此次操作的代价 \(v\)，再把 \(j\times z+v\) 插入大根堆。