http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=572&pid=1002
看完电影后，乐乐回家玩起了积木。
他已经搭好了n堆积木，他想通过调整积木，使得其中有连续W堆积木具有相同的高度，同时他希望高度恰好为H。
乐乐的积木都这了，也就是说不能添加新的积木，只能移动现有的积木。
他可以把一个积木从一堆移动到另一堆或者新的一堆，但是不能移动到两堆之间。比如，一次移动之后，"3 2 3" 可以变成 "2 2 4" 或者 "3 2 2 1",但是不能变成"3 1 1 3".
请你帮他算算，需要移动的最少积木数。
1.枚举求出每w堆需要最少移动的积木数，max（高变矮需要的数目，矮变高需要的数目），在求出最小值
2.需要输入优化
3.最终选取的W堆积木中，有可能有几堆原本不存在。如 9 8 7 形成3*3，可把3堆积木变成5堆 3 3 3 8 7，最少移动6个积木。因此需要在n堆积木两端补上W个0。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define ll long long #define maxn 50050 #define min(a,b) a<b?a:b #define max(a,b) a>b?a:b ll n,w,h; ll a[maxn*3]; 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("%d%d%d",&n,&w,&h)) { 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 positive=0,negative=0,mi; for(int i=0;i<w;i++)a[i]>h?positive+=a[i]-h:negative+=h-a[i]; mi=max(positive,negative); for(int i=w;i<n+2*w;i++) { a[i]>h?positive+=a[i]-h:negative+=h-a[i]; a[i-w]>h?positive-=a[i-w]-h:negative-=h-a[i-w]; ll tmp=max(positive,negative); mi=min(mi,tmp); } printf("%lld\n",mi); } return 0; } /* 3 3 3 9 8 7 */
原文：http://www.cnblogs.com/kylehz/p/4358352.html