自动搬运

查看原文

来自洛谷，原作者为

	ButterflyDew life is hard

搬运于2025-08-24 21:43:08，当前版本为作者最后更新于2018-08-28 17:42:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种$nlogn$的神奇做法

先说操作（以单调非降为例）： 从左到右，把当前位置的数放进大根堆，然后比较这个数和堆顶的大小。

若比堆顶大，就不管

若比堆顶小，就把堆顶拿出来变成这个数，然后答案增加堆顶与这个数的差

代码大概是这样

for(int i=1;i<=n;i++)
{
    scanf("%d",&a);
    q.push(a);
    if(a<q.top())
    {
        ans+=q.top()-a;
        q.pop();
        q.push(a);
    }
}

为什么捏？

假设塞到第$i$了，前面是一个合法的递增序列，堆顶为$y$，当前为$x$且$x<y$

这时候我们花掉了$y-x$块钱进行调整，考虑我们调整可以得到哪些结果

二元组$(x,x),(x+1,x+1),..(y-1,y-1),(y,y)$都是可能的结果，虽然有的结果可能不合法，但一定存在合法的结果

我们尽可能想让当前的数值小，所以我们尽可能会选择小的合法结果

这时候我们发现，如果堆顶在后面被更新了，我们的合法结果的选择集合就变了

如果我们直接把最小的可能不合法的结果放进堆，那么当比它大的元素都被砍掉后（也就是它成了堆顶），它就变得合法了