题解 P2234 【[HNOI2002]营业额统计】

2017-09-19 16:50:04


没有树状数组的题解的话那就让我来写一个吧。。

优点:码量短,适合不会stl的蒟蒻选手。

#include<bits/stdc++.h>
using namespace std;
int n,x,sum,ans,f1[5000000],f2[5000000];
int read(){
    char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
    int k=1,kk=0;if (c=='-')k=-1;else kk=c-'0';c=getchar();
    while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return kk*k;
}void putit1(int x){for (int i=x;i<=3000000;i+=i&(-i))f1[i]=max(f1[i],x);}
void putit2(int x){for (int i=x;i<=3000000;i+=i&(-i))f2[i]=max(f2[i],x);}
int findit1(int x){int ans=-1e9;for (;x;x-=x&(-x))ans=max(ans,f1[x]);return ans;}
int findit2(int x){int ans=-1e9;for (;x;x-=x&(-x))ans=max(ans,f2[x]);return ans;}
signed main(){
    memset(f1,200,sizeof(f1));memset(f2,200,sizeof(f2));//最小值不一定是0所以要初始化(我被坑了
    n=read();ans=read();putit1(ans+1500000);putit2(1500000-ans);
    for (int i=2;i<=n;i++){
        x=read()+1500000;sum=x-findit1(x);putit1(x);//在小于x的元素中找最大的
        x=3000000-x;sum=min(sum,x-findit2(x));putit2(x);//在大于x的元素中找最小的
        ans+=sum;
    }cout<<ans<<endl;
}