HZOJ trade

强烈谴责$skyh$的没$Huge 脸$行为。

很经典的可反悔贪心，然而我一直以为是sbdp还一直想着怎么优化……

正常的贪心肯定是不对的。

但是由于A-C=A-B+B-C，

所以用一个小根堆维护，每次将当前天的a加入，表示当前天可以买入，

如果堆顶小于a，取出堆顶，ans加上差，再次将当天的a加入，那么如果之后卖出更优则会减掉当前的a利用差价满足了贪心性质。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define int LL
#define LL long long
using namespace std;
int n,a[100010];

inline int read();
signed main()//dp xds//优化dp//单调
{
//    freopen("trade14.in","r",stdin);

    n=read();for(int i=1;i<=n;i++)a[i]=read();
    
    priority_queue<int,vector<int>,greater<int> >A;
    LL ans=0;A.push(a[1]);
    for(int i=2;i<=n;i++)
    {
        if(A.top()<a[i])
        {
            ans+=a[i]-A.top();A.pop();
            A.push(a[i]);
        }
        A.push(a[i]);
    }
    printf("%lld
",ans);
}
inline int read()
{
    int s=0,f=1;char a=getchar();
    while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();}
    while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
    return s*f;
}