HDU5191 – Building Blocks(扫描)

题目链接：HDU5191

【题意】看完电影后，乐乐回家玩起了积木。
他已经搭好了n堆积木，他想通过调整积木，使得其中有连续W堆积木具有相同的高度，同时他希望高度恰好为H。
乐乐的积木都这了，也就是说不能添加新的积木，只能移动现有的积木。
他可以把一个积木从一堆移动到另一堆或者新的一堆，但是不能移动到两堆之间。比如，一次移动之后，”3 2 3″ 可以变成 “2 2 4” 或者 “3 2 2 1″,但是不能变成”3 1 1 3”.
请你帮他算算，需要移动的最少积木数。所有整数范围都在[1,50000]

【分析】官方题解说的很清楚了，比赛的时候脑抽了，竟然想成区间所有a[i]-h的绝对值/2了，可以用两个前缀和分别记录比h大的和比h小的差值和，然后枚举每段连续区间较大的就可以，有个需要注意，存在w-n>=2的时候，需要考虑左右两边都补上0。

【AC CODE】686ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10;
LL sum1[MAXN],sum2[MAXN];

int in()
{
	int ch;
	while((ch = getchar()) < '0' || ch > '9');
	int ans = ch-'0';
	while((ch = getchar()) >= '0' && ch <= '9') ans = (ans<<1)+(ans<<3)+ch-'0';
	return ans;
}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int n;
	LL w,h;
	while(~scanf("%d %I64d %I64d%*c", &n, &w, &h))
	{
		LL sum = 0;
		repe(i,1,n)
		{
			LL a = in();
			sum1[i] = sum1[i-1];
			sum2[i] = sum2[i-1];
			if(a > h) sum1[i] += a-h;
			else sum2[i] += h-a;
			sum += a;
		}
		LL ans = h*w;
		if(ans > sum)
		{
			puts("-1");
			continue;
		}
		rep(i,1,n+w)
		{
			LL s1 = 0,s2 = 0;
			if(i-w >= 0 && i <= n)
			{
				s1 = sum1[i]-sum1[i-w];
				s2 = sum2[i]-sum2[i-w];
			}
			if(i-w < 0)
			{
				s1 = sum1[i];
				s2 = sum2[i]+(w-i)*h;
			}
			if(i > n)
			{
				s1 += sum1[n]-(i-w >= 0?sum1[i-w]:0);
				s2 += sum2[n]-(i-w >= 0?sum2[i-w]:0)+(i-n)*h;
			}
			ans = min(ans, max(s1,s2));
		}
		printf("%I64d\n", ans);
	}
	return 0;
}
/*
4 3 2
1 2 3 5
4 4 4
1 2 3 4
4 50 2
1 200 3 5
4 3 1
1 20 1 1
5 3 2
2 1 1 3 2
3 3 3
5 5 5
5 3 2
2 2 1 1 3
1 50000 50000
1
======================
1
-1
96
1
1
4
1
-1
*/