hdu5191Building Blocks 模拟

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

题解：在原区间两侧各加一个长为w的全0序列，维护从0到i的一个区间全加数jia[i] 和 全减数cha[i],(完成这段区间只添加/减少所需),则区间0到i的答案为max(jia[i],cha[i]).时间卡的比较紧，使用快速读写。

代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N  =  50000*3+100;
typedef long long ll;
const ll inf = 1e16;
ll sum,cha[N],jia[N],ans;
int n;
ll m,w;
int a[N],b;
void in(int &x){
    char ch; int minus = 0;
    while (ch=getchar(), (ch<'0'||ch>'9') && ch!='-');
    if (ch == '-') minus = 1, x = 0;
    else x = ch-'0';
    while (ch=getchar(), ch>='0'&&ch<='9') x = x*10+ch-'0';
    if (minus) x = -x;
}
void in(ll &x){
    char ch; int minus = 0;
    while (ch=getchar(), (ch<'0'||ch>'9') && ch!='-');
    if (ch == '-') minus = 1, x = 0;
    else x = ch-'0';
    while (ch=getchar(), ch>='0'&&ch<='9') x = x*10+ch-'0';
    if (minus) x = -x;
}
void out(int x){
    char hc[30];int len, minus=0;
    if (x<0) minus = 1, x = -x;
    len = 0; hc[len++] = x%10+'0';
    while (x/=10) hc[len++] = x%10+'0';
    if (minus) putchar('-');
    for (int i=len-1; i>=0; i--) putchar(hc[i]);
}
void out(ll x){
    char hc[30];int len, minus=0;
    if (x<0) minus = 1, x = -x;
    len = 0; hc[len++] = x%10+'0';
    while (x/=10) hc[len++] = x%10+'0';
    if (minus) putchar('-');
    for (int i=len-1; i>=0; i--) putchar(hc[i]);
}
int main()
{
    while(scanf("%d%lld%lld",&n,&m,&w)!=EOF){
        sum = 0;cha[0]=0;jia[0]=0;
        ans = inf;
        for(int i=1;i<=n;i++) in(a[i+m]);
        for(int i=1;i<=m;i++) a[i+n+m]=a[i]=0;
        for(int i=1;i<=n+m*2;i++){
            sum+=a[i];
            ll b=w-a[i];
            if(b>0)
                cha[i] = cha[i-1]+b , jia[i]=jia[i-1];
            else
                jia[i] = jia[i-1]-b , cha[i] = cha[i-1];
        }
        if(sum < m*w ){puts("-1");continue;}
        for(int i=1;i<=n+m+1;i++){
            ll tmp = max(cha[i+m-1]-cha[i-1],jia[i+m-1]-jia[i-1]);
            ans = min(tmp,ans);
        }
        out(ans);putchar('\n');
    }
    return 0;
}

hdu5191Building Blocks 模拟

原文：http://blog.csdn.net/alpc_wt/article/details/44537371