题解 P2893 【[USACO08FEB]修路Making the Grade】

· · 题解

提供一种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)都是可能的结果，虽然有的结果可能不合法，但一定存在合法的结果

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

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

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