hdu 5191(思路题)

Building Blocks

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2209    Accepted Submission(s): 509

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, about 100 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

BestCoder Round #34

 

题意:在一个区间里面进行块的增删,让某段长度为W的区间高度都为H，每次移动一块,问最少要移动多少次?

题解:刚开始漏看了每次移动一块这个条件,打死也做不出来..这个题目的解法就是区间的移动,左端点删除以及右端点的添加来维护所有长度为W的区间,但是要在前面和后面添W个0块，因为我们有可能是往两边补。维护两个变量,一个是把高变矮 t，一个是把矮变高 s,最开始的区间是[1,W]，这个区间我们要将矮的变高,所以最开始我们 s = w*h ,ans =w*h
,然后我们的区间右移到[2,W+1]，这时我们要把1删除,然后将w+1添加进去,这样的话对 s,t进行加减，然后取个大值就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = 200005;
LL n,w,h;
LL high[N];
int main()
{
    while(scanf("%lld%lld%lld",&n,&w,&h)!=EOF){
        LL sum = 0;
        memset(high,0,sizeof(high));
        for(int i=1;i<w+1;i++){
            high[i]-=h;
        }
        for(int i=w+1;i<w+1+n;i++){
            scanf("%lld",&high[i]);
            sum+=high[i];
            high[i]-=h;
        }
        for(int i=w+1+n;i<=w+w+n;i++){
            high[i]-=h;
        }
        if(sum<h*w){
            printf("-1
");
            continue;
        }
        LL s=w*h,t=0,ans = w*h; ///s维护将高的拿走,t维护将矮的补上,最开始[1,w]要补w*h进去,所以ans初始化w*h
        for(int i=w+1;i<=w+w+n;i++){
            if(high[i-w]>0) t-=high[i-w]; ///删除第 i-w 块
            else s+=high[i-w];
            if(high[i]>0) t+=high[i]; ///添加第 i 块
            else s-=high[i];
            ans = min(ans,max(t,s));
        }
        printf("%lld
",ans);
    }
    return 0;
}