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

Starria的脑残粉

2017-09-19 16:50:04

Solution

没有树状数组的题解的话那就让我来写一个吧。。 优点:码量短,适合不会stl的蒟蒻选手。 ```cpp #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; } ```