bzoj1112 [POI2008]砖块Klo

网友投稿 794 2022-08-29

bzoj1112 [POI2008]砖块Klo

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 Sample Output

2

我设置两个map 然后他们一共两个关键字 把map当堆用 每次堆2的堆顶就是我们的中位数 然后新入的数根据 堆2 中堆顶元素决定插入哪个堆 但是有可能我有个堆消失了 那么我们需要动态去调整一下 一边做一边统计答案即可

#include#include#include#includeusing namespace std;#define N 110000inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}mapq1,q2;int n,k,h[N],a[N],size2,size1;long long ans,s1,s2;inline void change(){ if (size2-size1>k%2){ int top2;top2=q2.begin()->first; s2-=top2;size2--; if (--q2[top2]==0) q2.erase(top2); s1+=top2;size1++; q1[top2]++; }else if(size2-size1::iterator ii;int top1; ii=q1.end();--ii;top1=ii->first; s1-=top1;size1--; if (--q1[top1]==0) q1.erase(top1); s2+=top1;size2++; q2[top1]++; }}int main(){ freopen("bzoj1112.in","r",stdin); n=read();k=read(); for (int i=1;i<=n;++i) h[i]=read(); for (int i=1;i<=k;++i) a[i]=h[i]; sort(a+1,a+k+1); for (int i=1;i<=(k>>1);++i) q1[a[i]]++,s1+=a[i];size1=k>>1,size2=k-(k>>1); for (int i=(k/2)+1;i<=k;++i) q2[a[i]]++,s2+=a[i]; map::iterator ii; //for (ii=q1.begin();ii!=q1.end();ii++) printf("%d\n",ii->first); //for (ii=q2.begin();ii!=q2.end();ii++) printf("%d\n",ii->first); //int tmp=q1.begin()->first,tmp1=q1.end()->second; //int tmp2=q2.begin()->second,tmp3=q2.end()->second; //printf("%d %d %d %d \n",tmp,tmp1,tmp2,tmp3); //int top2=q2.begin()->first;ii=q1.end();ii--;int top1=ii->first; int mid=q2.begin()->first; ans=-s1+s2-k%2*mid; //printf("%lld %d %d\n",ans,top1,top2); for (int i=k+1;i<=n;++i){ if (h[i-k]>=mid){ s2-=h[i-k];size2--; if (--q2[h[i-k]]==0) q2.erase(h[i-k]); }else{ s1-=h[i-k];size1--; if (--q1[h[i-k]]==0) q1.erase(h[i-k]); }/*printf("-----\n");printf("堆1\n"); for (ii=q1.begin();ii!=q1.end();ii++) printf("%d\n",ii->first);printf("堆2\n"); for (ii=q2.begin();ii!=q2.end();ii++) printf("%d\n",ii->first); printf("-----\n");*/ if (h[i]>=mid){ s2+=h[i];size2++; q2[h[i]]++; }else{ s1+=h[i];size1++; q1[h[i]]++; } change(); //long long ans1=0;ii=q1.end();ii--;int top1=ii->first; long long ans1=0; mid=q2.begin()->first; ans1=-s1+s2-k%2*mid; ans=min(ans1,ans);/*printf("-----\n");printf("堆1\n"); for (ii=q1.begin();ii!=q1.end();ii++) printf("%d\n",ii->first);printf("堆2\n"); for (ii=q2.begin();ii!=q2.end();ii++) printf("%d\n",ii->first); printf("-----\n"); printf("%lld %lld\n",ans1,ans);*/ } printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：统计
上一篇:codeforces 486d Valid Sets
下一篇:阿里产品专家：高情商的技术人，如何做沟通？
相关文章

 发表评论

暂时没有评论，来抢沙发吧~