Building BlocksTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 281Accepted Submission(s): 59
Problem Description
After enjoying the movie,LeLe went home alone. LeLe decided to build blocks.LeLe has already builtpiles. He wants to move some blocks to makeconsecutive piles with exactly the same height.LeLe already put all of his blocks in these piles, which means he can not add any blocks into them. Besides, he can move a block from one pile to another or a new one，but not the position betweens two piles already exists.For instance,after one move,"3 2 3" can become "2 2 4" or "3 2 2 1",but not "3 1 1 3".You are request to calculate the minimum blocks should LeLe move.
Input
There are multiple test cases, aboutcases.The first line of input contains three integerspiles blocks.For the next line ,there areindicate the height of each piles.The height of a block is 1.
Output
Output the minimum number of blocks should LeLe move.If there is no solution, output "-1" (without quotes).
Sample Input
4 3 21 2 3 54 4 41 2 3 4
Sample Output
1-1
Hint
In first case, LeLe move one block from third pile to first pile.
Source
Recommend
hujie|We have carefully selected several similar problems for you:51935192518951885185
题意：有n堆由1*1小木块堆起来的积木，现在要你移动若干次使其中连续的长度为w的高度都为h，一次只能移动一个，而且可以在两边增加新堆（只能在两边，不能在中间插入），问最少得移动多少次。
思路：因为可以在两边增加堆，所以我先在数组两边各加上w长度，Move数组存 每个地方变成h要移进来或者移出去的步数，a数组记录i位子是要移进来还是移出去。然后维护一个长度为w的连续区间（i-w+1 ~ i），计算出这个区间总共得移进来的数目z和移出去的数目和f，，那么要使这个区间满足条件就要移动m=z+f-min（z，f），（这里减去min（z，f）是因为移进来和移出去可以抵消一部分）。比赛时用的G++交的，结果终判超时挂了！后来用C++交就过了！！！
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 150010#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;ll n,w,h;ll Move[maxn];bool a[maxn];int main(){ll i,j,x;while (~scanf("%lld%lld%lld",&n,&w,&h)){ll sum=0,m;FRL(i,0,n+2*w)a[i]=false;FRE(i,w+1,n+w){scanf("%lld",&x);Move[i]=abs(h-x);if (h<x) a[i]=true;sum+=x;}if (w*h>sum){pf("-1\n");continue;}ll z=0,f=0;FRE(i,1,w)//前后扩大Move[i]=h;FRE(i,n+w+1,n+2*w)Move[i]=h;z=w*h;f=0;m=z+f-min(z,f);ll ans=m;FRE(i,w+1,n+2*w) //枚举区间{if (a[i-w]) //要除去前面一个区间的第一个数（往后移动它就出了嘛）f-=Move[i-w];elsez-=Move[i-w];if (a[i])//加上新进来的f+=Move[i];elsez+=Move[i];m=z+f-min(z,f);ans=min(ans,m);}pf("%lld\n",ans);}return 0;}
游手好闲会使人心智生锈
