首页 > 代码库 > BZOJ 1112: [POI2008]砖块Klo
BZOJ 1112: [POI2008]砖块Klo
Description
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
Input
第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000
题解：
如果确定了将区间[l,r]变成一样的，那么变成中位数需要的操作次数最少。
可以用平衡树维护，支持查询第k大、查询小于k大数的和、查询大于k大数的和，利用这些可以快速的求出答案。
复杂度`O(nlogn)`。注意开LL。
代码：
(平衡树写的渣。)
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>//by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);LL n,k;LL a[100005];LL num[100005],sum[100005],ls[100005],rs[100005],val[100005],fa[100005],siz[100005];inline void upd(int o){ siz[o]=siz[ls[o]]+siz[rs[o]]+num[o]; sum[o]=num[o]*val[o]+sum[ls[o]]+sum[rs[o]];}inline void zig(int x){ int y=fa[x]; if(rs[x]) ls[y]=rs[x],fa[rs[x]]=y; else ls[y]=0; fa[x]=fa[y]; if(fa[y]){ if(ls[fa[y]]==y) ls[fa[y]]=x;else rs[fa[y]]=x; } fa[y]=x;rs[x]=y; upd(y);}inline void zag(int x){ int y=fa[x]; if(ls[x]) rs[y]=ls[x],fa[ls[x]]=y; else rs[y]=0; fa[x]=fa[y]; if(fa[y]){ if(ls[fa[y]]==y) ls[fa[y]]=x;else rs[fa[y]]=x; } fa[y]=x;ls[x]=y; upd(y);}int root;inline void splay(int x,int z){ while(fa[x]!=z){ int y=fa[x]; if(fa[y]==z){ if(ls[y]==x) zig(x); else zag(x); }else{ if(ls[fa[y]]==y){ if(ls[y]==x){ zig(y),zig(x); }else{ zag(x);zig(x); } }else{ if(ls[y]==x){ zig(x),zag(x); }else{ zag(y),zag(x); } } } } if(!z) root=x; upd(x);}int c;inline void insert(LL x){ int o=root; int f=0; while(o){ f=o; if(val[o]==x){ num[o]++; splay(o,0); return; } if(x<val[o]){ o=ls[o]; }else{ o=rs[o]; } } o=++c; if(f){ if(x<val[f]){ ls[f]=o; }else{ rs[f]=o; } }else root=o; fa[o]=f; val[o]=x; num[o]=1; splay(o,0);}inline void del(LL x){ int o=root; while(1){ if(val[o]==x){ num[o]--; splay(o,0); return; } if(x<val[o]){ o=ls[o]; }else o=rs[o]; }}inline void ask(int k){ int o=root; while(1){ if(siz[ls[o]]>=k) { o=ls[o];continue; } if(siz[ls[o]]+num[o]>=k) { splay(o,0);return; }else{ k-=siz[ls[o]]+num[o]; o=rs[o]; } }}LL ans;int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif ans=inf*1LL*1000000; scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } for(int i=1;i<k;i++){ insert(a[i]); } for(int i=k;i<=n;i++){ if(i>k){ del(a[i-k]); } insert(a[i]); ask((k+1)/2); LL aim=val[root]; ans=min(ans,siz[ls[root]]*aim-sum[ls[root]]+sum[rs[root]]-siz[rs[root]]*aim); } printf("%lld\n",ans); return 0;}
BZOJ 1112: [POI2008]砖块Klo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。