Building Blocks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 829 Accepted Submission(s): 186
Problem Description
After enjoying the movie,LeLe went home alone. LeLe decided to build blocks.
LeLe has already built n
piles. He wants to move some blocks to make W
consecutive piles with exactly the same height H.
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, about100
cases.
The first line of input contains three integers n,W,H(1≤n,W,H≤50000).n
indicate n
piles blocks.
For the next line ,there are n
integers A1,A2,A3,……,An
indicate the height of each piles. (1≤Ai≤50000)
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 2
1 2 3 5
4 4 4
1 2 3 4
Sample Output
1
-1
Hint
In first case, LeLe move one block from third pile to first pile.
Source
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5191
题目大意：n堆木块，每个木块高为1，第i堆高ai，现在要求组成连续w个高度为h的木堆，最少移动几个木块，注意不能添加木块，且移动时，不可移动置两已存在的堆之间
题目分析：枚举区间w的位置，因为要考虑ai的最小值都大于h的情况，因此我们需要将区间分成三段[1 - w], [w+1, w+n], [w+n, w+w+n]，动态维护区间w，用t1，t2表示当前区间内需要加入的和需要移出的木块数，区间每移动一次，头尾两个值要修改，下面给出样例1动态维护的过程：
0 0 0 1 2 3 5 0 0 0
t1 6 6 6 5 3 1 0 2 4 6
t2 0 0 0 0 0 1 4 4 3 0
交的时候用C++交
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MAX = 150005;
ll a[MAX];
int main()
{
ll n, w, h;
while(scanf("%I64d %I64d %I64d", &n, &w, &h) != EOF)
{
ll sum = 0;
memset(a, 0, sizeof(a));
for(int i = w + 1; i <= w + n; i++)
{
scanf("%I64d", &a[i]);
sum += a[i];
}
if(sum < h * w)
{
printf("-1\n");
continue;
}
ll t1 = w * h, ans = w * h, t2 = 0;
for(int i = w + 1; i <= w + w + n; i++)
{
if(a[i - w] < h)
t1 -= (h - a[i - w]);
else
t2 -= (a[i - w] - h);
if(a[i] < h)
t1 += (h - a[i]);
else
t2 += (a[i] - h);
ans = min(ans, max(t1, t2));
}
printf("%I64d\n", ans);
}
}
HDU 5191 Building Blocks (模拟)
原文：http://blog.csdn.net/tc_to_top/article/details/44536011
