「BZOJ1112」[POI2008] 砖块Klo
Description
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
Input
第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000
Output
最小的动作次数
Sample Input
5 3
3
9
2
3
1
3
9
2
3
1
Sample Output
2
HINT
原题还要求输出结束状态时,每柱砖的高度.本题略去.
题解
据说有很多做法，有一些基于h[i]<=10^6
不过平衡树的做法还是比较容易想的
可以这样考虑
首先如果确定了一个区间，我们只需要求出区间中位数，可以枚举区间并在logn的时间内获得中位数
那么我们需要一种数据结构，支持插入删除，以及logn查询区间k大
平衡树可以实现，并且在获得中位数x时得出大/小等于x的数的个数以及和，就可以获得这个区间的最优值
也就是平衡树不仅要维护子树的大小，还要维护权值和
注意开longlong
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #define ll long long #define linf 9223372036854775807LL using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,K,m,root,sz; ll tmp; ll ans=linf,sum1,sum2; int h[100005]; int rnd[100005],size[100005],l[100005],r[100005],w[100005]; ll sum[100005],v[100005]; void update(int k) { size[k]=size[l[k]]+size[r[k]]+w[k]; sum[k]=sum[l[k]]+sum[r[k]]+v[k]*w[k]; } void rturn(int &k) {int t=l[k];l[k]=r[t];r[t]=k;update(k);update(t);k=t;} void lturn(int &k) {int t=r[k];r[k]=l[t];l[t]=k;update(k);update(t);k=t;} void insert(int &k,int val) { if(!k){k=++sz;sum[k]=v[k]=val;w[k]=size[k]=1;rnd[k]=rand();return;} size[k]++;sum[k]+=val; if(val==v[k])w[k]++; else if(val<v[k]) {insert(l[k],val);if(rnd[l[k]]<rnd[k])rturn(k);} else {insert(r[k],val);if(rnd[r[k]]<rnd[k])lturn(k);} } void del(int &k,int val) { if(!k)return; if(val==v[k]) { if(w[k]>1){w[k]--;sum[k]-=val;size[k]--;return;} if(l[k]*r[k]==0)k=l[k]+r[k]; else if(rnd[l[k]]<rnd[r[k]]){rturn(k);del(k,val);} else {lturn(k);del(k,val);} } else if(val<v[k]) {size[k]--;sum[k]-=val;del(l[k],val);} else {size[k]--;sum[k]-=val;del(r[k],val);} } void find(int k,int rank) { if(!k)return; if(rank>size[l[k]]&&rank<=size[l[k]]+w[k]) { sum1+=(sum[l[k]]+(rank-size[l[k]]-1)*v[k]); sum2+=(sum[r[k]]+(size[l[k]]+w[k]-rank)*v[k]); tmp=v[k]; } else if(rank<=size[l[k]]) { sum2+=(v[k]*w[k]+sum[r[k]]); find(l[k],rank); } else { sum1+=(v[k]*w[k]+sum[l[k]]); find(r[k],rank-size[l[k]]-w[k]); } } void getans() { sum1=sum2=0; find(root,m); ll sum=(m-1)*tmp-sum1+sum2-(K-m)*tmp; if(sum<ans)ans=sum; } int main() { n=read(),K=read();m=((K+1)>>1); for(int i=1;i<=n;i++) h[i]=read(); for(int i=1;i<=K;i++) insert(root,h[i]); getans(); for(int i=K+1;i<=n;i++) { del(root,h[i-K]); insert(root,h[i]); getans(); } printf("%lld",ans); return 0; } |
计数器 9319208
OI 课件=>
OI 课件=>
在删除操作中，旋转后继续执行的如果是 del(r
,val)或del(l 
,val)行不行？
我发现这样是会WA的，求教神犇这是为什么QAQ
自行模拟TAT