本文共 2372 字，大约阅读时间需要 7 分钟。
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000
最小的动作次数
#include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;ll ans;int n,k;int s[100010];struct treap{ treap *ls,*rs; int size; int val; int rnd; ll sum; treap(){} treap(treap *son,int v) { ls=rs=son; size=1; val=v; sum=1ll*v; rnd=rand(); } void pushup() { sum=ls->sum+rs->sum+val; size=ls->size+rs->size+1; }}tr[100010],nil;typedef treap* node;node root,null,cnt;node a,b,c;inline void init(){ nil=treap(NULL,0); null=&nil; null->ls=null->rs=null; null->size=0; root=null; cnt=tr;}inline node build(int v){ *cnt=treap(null,v); return cnt++;}inline node merge(node x,node y){ if(x==null) { return y; } if(y==null) { return x; } if(x->rnd rnd) { x->rs=merge(x->rs,y); x->pushup(); return x; } else { y->ls=merge(x,y->ls); y->pushup(); return y; }}inline void split1(node rt,node &x,node &y,int k){ if(rt==null) { x=y=null; return ; } if(rt->ls->size>=k) { y=rt; split1(rt->ls,x,y->ls,k); } else { x=rt; split1(rt->rs,x->rs,y,k-1-rt->ls->size); } rt->pushup();}inline void split2(node rt,node &x,node &y,int k){ if(rt==null) { x=y=null; return ; } if(rt->val>=k) { y=rt; split2(rt->ls,x,y->ls,k); } else { x=rt; split2(rt->rs,x->rs,y,k); } rt->pushup();}inline void query(){ split1(root,a,b,k/2); split1(b,b,c,1); ll res=1ll*a->size*b->val-a->sum; res+=c->sum-1ll*c->size*b->val; ans=min(res,ans); root=merge(merge(a,b),c);}int main(){ srand(12378); scanf("%d%d",&n,&k); ans=1ll<<60; init(); for(int i=1;i<=n;i++) { scanf("%d",&s[i]); } for(int i=1;i<=k;i++) { split2(root,a,b,s[i]); root=merge(merge(a,build(s[i])),b); } query(); for(int i=k+1;i<=n;i++) { split2(root,a,b,s[i-k]); split1(b,b,c,1); root=merge(a,c); split2(root,a,b,s[i]); root=merge(merge(a,build(s[i])),b); query(); } printf("%lld",ans);}
转载于:https://www.cnblogs.com/Khada-Jhin/p/10731075.html