题解 P4597 【序列sequence】

· · 题解

表示完全看不懂楼下的大佬们说啥……特别是某绿……某c姓大佬

来说说个人的理解吧

大佬们说：考虑当前的数x和之前的最大数y，（默认x<y，因为如果x>=y已经满足非降了）为了让它非降，我们要在区间[x,y]里找到一个数z，使y减小到z,x增大到z，那么可以发现，不管取的数是什么，代价都是y-x

不难看出，y减小的越多，后面的序列越容易变成非降，那么只要让y减小到x就好了

看到这里，我一直有一个疑问，如果令y减小到x之后，序列不满足非降了怎么办？

仔细想了想，实际上应该是这样的：为了让序列非降，y不能小于y之前的最大值。而由于y是整个序列的最大值，如果它之前的最大值z小于等于x，那么将y减小到x仍能保证序列是非降的。否则的话，z大于x小于y，仍是在区间[x,y]内，那么移动的代价是y-x，所以用于更新答案是没有问题的

那么这里为什么要让y减到最小呢？这是因为x和y不论如何调整，他们的代价之和都已经不变了，但问题是他们目前选的最优方案并不是之后的最优。为了满足他们在之后最优，只有把y减小到x，才能保证之后更有可能非降。

概括一下，对于当前的数，无论最优解如何，对答案的贡献是一定的。而为了保证之后的解也最优，令y减小到x，可以保证之后的解最优，且不会影响当前的最优解

代码好短……

//minamoto
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
priority_queue<int> q;
int n;long long ans;
int main(){
    n=read();
    while(n--){
        int x=read();q.push(x);
        if(x<q.top()){
            ans+=q.top()-x;
            q.pop();q.push(x);
        }
    }
    printf("%lld\n",ans);
    return 0;
}