hdu 5191-Building Blocks

题目及代码：

题目的意思是有n堆积木，每堆积木上有一定数目的积木，现在我想移动一些积木（每次移动一个），可以用一些积木重新添加一堆积木，但不能在两堆之间添加，使得出现连续的W堆积木，每堆的数目为H。

由于的连续的W堆，那么这样思路就好想了。我们首先求出第一组1-W堆中需要的最小数目（求法是求出这W堆中多于H的堆减去H的总和l和少于H的堆减去H的总和的绝对值r，取l和r中的最大值，想一想为什么？因为我们可以把多出来移到少的上面，如果说达到要求时，多的更多，那么多的还要移到别的地方去，移动次数就为l，反之少的更多，即不够了，那么我们还要从别的地方移进来，那么移动次数就是r），然后我们向后移动，每移动一次，减去过去最前面的值，然后加上新进来的值，也就是维护一个长为W的数组中的l和r，以求得最优解。

当然，这样还是不够。因为想出现3 3 3-9 8 7这种情况，我们可以新添加几堆来使得出现这样的情况：9 6 3 3 3，这样移动次数最佳。所以我们要在n长度的后面再添加长度W，值为0的数组。除了向后维护，其实向前也要维护，也就是在n长度的数组之前也要加上W长度的值为0的数组（想一想为什么）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

ll nt,mt[150010];
int main()
{
    ll n,M,H;
    while(scanf("%I64d%I64d%I64d",&n,&M,&H)!=EOF)
    {
        memset(mt,0,sizeof(mt));
        ll sum=0;
        for(int i=0;i<M;i++)
        {
            mt[i]=-H;
        }
        for(int i=M;i<n+M;i++)
        {
            scanf("%I64d",&nt);
            sum+=nt;
            mt[i]=nt-H;
        }
        for(int i=n+M;i<n+M+M;i++)
        {
            mt[i]=-H;
        }
        if(sum<M*H)
        {
            printf("-1\n");
            continue;
        }

        ll ans=M*H,l=M*H,r=0;
        for(int i=M;i<n+M+M;i++)
        {
            if(mt[i-M]<0) l+=mt[i-M];
            else r-=mt[i-M];
            if(mt[i]<0) l-=mt[i];
            else r+=mt[i];
            ans=min(ans,max(l,r));
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

hdu 5191-Building Blocks

原文：http://blog.csdn.net/knight_kaka/article/details/44539463