HDU 5191 Building Blocks

发表于   |   分类于   |     |   阅读次数

题目描述

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, about $100$ cases.

The first line of input contains three integers $n,W,H(1 \leq n,W,H \leq 50000)$.$n$ indicate $n$ piles blocks.

For the next line ,there are $n$ integers $A_1,A_2,A_3,……,A_n$ indicate the height of each piles. $(1 \leq A_i \leq 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.

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5191

解题思路

其实很简单，就是算出长度为$W$的区间的正数之和和负数之和，不断地更新最小值。每个区间需要添加的砖块的数量和减少的砖块的数量的总和分别用$x$和$y$表示，每次取$x$和$y$中最大的一个数作为满足要求的数值（因为只有操作这两者的最多次数才可以满足题目的要求），最后将这个数和MIN比较，取其中最小的一个输出即可。

AC代码

670MS/5528K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

ll a[500005];
int main()
{
    int n, w, h;
    ll sum = 0;
    while (~scanf("%d%d%d", &n, &w, &h))
    {
        sum = 0;
        memset(a, 0, sizeof(a));
        for (int i = w; i < n + w; i++)
        {
            scanf("%I64d", a + i);
            sum += a[i];
        }
        if (sum < (ll) w * h)
        {
            printf("-1\n");
        }
        else
        {
            ll x = w * h, y = 0;
            ll MIN = w * h;
            for (int i = w; i < n + w * 2; i++)
            {
                if (a[i - w] < h)
                    x -= h - a[i - w];
                else
                    y -= a[i - w] - h;

                if (a[i] < h)
                    x += h - a[i];
                else
                    y += a[i] - h;
                MIN = min(MIN, max(x, y));
            }
            printf("%I64d\n", MIN);
        }
    }
    return 0;
}