http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=572&pid=1003
乐乐又开始搭积木了。
他想在昨天搭完的积木上，重新搭建，使得其中有连续W堆积木具有相同的高度，同时他希望高度最少为H。
乐乐的积木都这了，也就是说不能添加新的积木，只能移动现有的积木。
他可以把一个积木从一堆移动到另一堆或者新的一堆，但是不能移动到两堆之间。比如，一次移动之后，"3 2 3" 可以变成 "2 2 4" 或者 "3 2 2 1",但是不能变成"3 1 1 3".
请你帮他算算，当搭建的高度h为多少时，需要移动的积木最少，如果有多个h满足条件，输出h的最大值。
1. 与第二题相同，最终选取的W堆积木中，有可能有几堆原本不存在。如 9 8 7 形成3*3，可把3堆积木变成5堆 3 3 3 8 7，最少移动6个积木。因此需要在n堆积木两端补上W个0。
2.需要输入优化
3.
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define ll long long #define maxn 50050*3 #define min(a,b) a<b?a:b #define max(a,b) a>b?a:b #define low(x) x&(-x) ll n,w,h; ll a[maxn+50]; ll c[maxn+50]; ll s[maxn+50]; void add(ll i,ll val) { int num=i; while(i<maxn) { c[i]+=val; s[i]+=num*val; i+=low(i); } } ll getsum(ll i) { ll sum=0; while(i>0) { sum+=s[i]; i-=low(i); } return sum; } ll getcnt(ll i) { ll sum=0; while(i>0) { sum+=c[i]; i-=low(i); } return sum; } bool check() { ll sum=0; for(int i=w; i<n+w; i++)sum+=a[i]; return sum>=w*h?true:false; } int getint() { int ret=0; bool ok=0,neg=0; for(;;) { int c=getchar(); if(c>=‘0‘&&c<=‘9‘)ret=(ret<<3)+ret+ret+c-‘0‘,ok=1; else if(ok)return neg?-ret:ret; else if(c==‘-‘)neg=1; } } int main() { while(~scanf("%lld%lld%lld",&n,&w,&h)) { memset(c,0,sizeof(c)); memset(s,0,sizeof(s)); for(int i=0; i<w; i++)a[i]=0; for(int i=w; i<n+w; i++)a[i]=getint(); for(int i=n+w; i<n+2*w; i++)a[i]=0; if(check()==false) { puts("-1"); continue; } ll mi=1000000000000000; ll sum,hh,positive,negative,pNum,nNum,tmp,hans,SUM; SUM=0; for(int i=w; i<n+w; i++)SUM+=a[i]; for(int i=0; i<w; i++)add(a[i]+1,1); for(int i=w; i<n+2*w; i++) { add(a[i]+1,1); add(a[i-w]+1,-1); sum=getsum(maxn)-w; hh=max(h,sum/w); nNum=getcnt(hh+1); pNum=w-nNum; negative=getsum(hh+1)-nNum; positive=sum-negative; // printf("** %lld %lld %lld\n",hh,positive-hh*pNum,hh*nNum-negative); tmp=max(positive-hh*pNum,hh*nNum-negative); if(tmp<mi) { mi=tmp; hans=hh; } else if(tmp==mi&&hh>hans) { hans=hh; } if((sum/w+1)*w>SUM)continue; hh=max(h,sum/w+1); nNum=getcnt(hh+1); pNum=w-nNum; negative=getsum(hh+1)-nNum; positive=sum-negative; // printf("** %lld %lld %lld\n",hh,positive-hh*pNum,hh*nNum-negative); tmp=max(positive-hh*pNum,hh*nNum-negative); if(tmp<mi) { mi=tmp; hans=hh; } else if(tmp==mi&&hh>hans) { hans=hh; } } printf("%lld %lld\n",hans,mi); } return 0; }
原文：http://www.cnblogs.com/kylehz/p/4360619.html