题目链接: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 */