nlogn堆做法，学dp的可以路过。

题目如上。

nlogn才能过的大数据：链接

本关卡需要的装备：堆+强大的思考

看了许多堆做法的题解，都只看的个半懂（就是因为我太弱了），最后自己模拟了一下就懂了？！

这里写一份自认为还算能一次看懂的题解:

我们可以分两次处理，一次处理递增的，另一次处理递减的，这里只说明递增的情况。

先上操作：

//q为大根堆，装b数列
for(int i=1;i<=n;i++)
{
    q.push(a[i]);
    if(a[i]<a.top())
    {   
        ans+=q.top()-a[i];
        q.pop();q.push(a[i]); 
    }
}

没错，核心代码就这些，要先看懂代码流程。

分析：

我们假设“最小花费”是s，x对应的b数列的值设为bx。

一开始，假如遇到前几个是递增的（只有一个也当作递增），那么就令bi=ai就好了。

然后新来了一个数x比前面b数列中的最大值数y小，不满足递增，只需让bx和by“互相靠近到一起”，使bx=by,就能满足s还是最小的。

详细点：

为什么y要取最大值，因为要满足递增，我们至少要让bx为最大值，而且by不变，这样s至少要加y-x，

如果不想让bx跑到y那么大，就应该让by小一点，假设减小了c，

这样bx能减c，但是因为by减c后又比y小了，所以bx变小让s减了c，但by的减少也让s加了c，所以s加的最小值就是y-x。

我们让x和y调整就够了，因为别的数一动就会使s增加。

那为了让未来更容易满组递增，应使bx和by越小越好，我们可以让by=x。

小结：
就是可以使

by=x;//q.pop();q.push(a[i]);
ans+=y-x;//ans+=q.top()-a[i];

Boss is coming！

问题来了，假设y之前的最大值为z，如果x<z<y,因为bz=z>x=by,那by=x会使b数列不满足递增，像这种情况：

调整前的b数列：

         y
       z
     -     x
   -
 -

调整后：

       z
     -   y x
   -
 -

我们先让它不满足，继续上面的处理方法，

现在突出来了一个z，我们等待着未来有一个新来的数把现在的最大值z拉下去，使序列合法。

如果到最后不合法，因为在调整x和y时，bx，by移到区间[x,y]中任意一个位置都能满足s加的最小，

而y>z>x,z在这个区间内，意味着我们可以最后将不合法的再调整到合法，而s不变。

补充：
为什么到这里仍取最大值y？

其实我们只是假设by=x这样最好的情况，实际上仍需取最大值满足递增，也就是让最后不合法的序列一定能调整到合法，并且s是最小的。

上面代码至此说明完毕。

完整代码：

下面是大根堆+小根堆分别处理递增和递减两种情况的代码。

当然，也可以分别从1到n，从n到1做两次递增的序列，不用开两个堆，从后往前做递增不就相当于从前往后做递减嘛。想做递减的还不是一样。这个代码在下下面。

#include<cstdio>
#include<queue>
using namespace std;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int mymin(int x,int y){return x<y?x:y;}
int n,a[2100],s1,s2;
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
int main()
{
    n=ri();
    for(int i=1;i<=n;i++)a[i]=ri();
    s1=s2=0;
    for(int i=1;i<=n;i++)
    {
        q1.push(a[i]);
        if(a[i]<q1.top())
        {
            s1+=q1.top()-a[i];
            q1.pop();q1.push(a[i]); 
        }
    }
    for(int i=1;i<=n;i++)
    {
        q2.push(a[i]);
        if(a[i]>q2.top())
        {
            s2+=a[i]-q2.top();
            q2.pop();q2.push(a[i]);
        }
    }
    printf("%d\n",mymin(s1,s2));
    return 0;
}

#include<cstdio>
#include<queue>
using namespace std;
int ri()
{
    char c=getchar();int s=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int mymin(int x,int y){return x<y?x:y;}
int n,a[2100],s1,s2;
priority_queue<int>q;
int main()
{
    n=ri();
    for(int i=1;i<=n;i++)a[i]=ri();
    s1=s2=0;
    for(int i=1;i<=n;i++)
    {
        q.push(a[i]);
        if(a[i]<q.top())
        {
            s1+=q.top()-a[i];
            q.pop();q.push(a[i]);
        }
    }
    while(!q.empty())q.pop();
    for(int i=n;i>=1;i--)
    {
        q.push(a[i]);
        if(a[i]<q.top())
        {
            s2+=q.top()-a[i];
            q.pop();q.push(a[i]);
        }
    }
    printf("%d\n",mymin(s1,s2));
    return 0;
}