题解：
和bzoj1367差不多
然后a[i]-i不用加
然后我再另一个地方加了这句话
然后poj ac,bzoj wa
poj数据水啊
代码：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=1000005; long long ans,ans1,ans2; int rt[N],cnt,r[N],c[N][2],dist[N],val[N],tot,size[N],n,a[N],l[N]; int merge(int x,int y) { if (!x||!y)return x+y; if (val[x]<val[y])swap(x,y); c[x][1]=merge(c[x][1],y); size[x]=size[c[x][0]]+size[c[x][1]]+1; if (dist[c[x][0]]<dist[c[x][1]])swap(c[x][0],c[x][1]); dist[x]=dist[c[x][1]]+1; return x; } void pop(int &x){x=merge(c[x][0],c[x][1]);} int newnode(int x) { val[++tot]=x; size[tot]=1; c[tot][0]=c[tot][1]=dist[tot]=0; return tot; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i=1;i<=n;i++) { rt[++cnt]=newnode(a[i]); l[cnt]=r[cnt]=i; while (cnt>1&&val[rt[cnt-1]]>val[rt[cnt]]) { cnt--; rt[cnt]=merge(rt[cnt],rt[cnt+1]); r[cnt]=r[cnt+1]; while (size[rt[cnt]]*2>r[cnt]-l[cnt]+2)pop(rt[cnt]); } } for (int i=1;i<=cnt;i++) { int t=val[rt[i]]; for (int j=l[i];j<=r[i];j++) ans1+=abs(t-a[j]); } ans=ans1; memset(val,0,sizeof val); memset(rt,0,sizeof rt); memset(c,0,sizeof c); memset(dist,0,sizeof dist); memset(l,0,sizeof l); memset(r,0,sizeof r); memset(size,0,sizeof size); tot=cnt=0; for (int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]); for (int i=1;i<=n;i++) { rt[++cnt]=newnode(a[i]); l[cnt]=r[cnt]=i; while (cnt>1&&val[rt[cnt-1]]>val[rt[cnt]]) { cnt--; rt[cnt]=merge(rt[cnt],rt[cnt+1]); r[cnt]=r[cnt+1]; while (size[rt[cnt]]*2>r[cnt]-l[cnt]+2)pop(rt[cnt]); } } for (int i=1;i<=cnt;i++) { int t=val[rt[i]]; for (int j=l[i];j<=r[i];j++) ans2+=abs(t-a[j]); } ans=min(ans,ans2); printf("%lld",ans); }