hdu5191

求获得这样的区间：连续w个元素值都为h，的最小移动次数。

扫一遍，每次处理w区间，更新最小。预处理出和。  注意long long，注意数组开大点，比赛因为数组少开了一倍。。因为前后都可以扩展出W。还好成功hack一些人。。保持rating。。

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
long long n,w,h;
long long sums[300600];
long long sumout[350560];
long long mins=50000*50000;
int main()
{
    while(~scanf("%I64d%I64d%I64d",&n,&w,&h))
    {
        int aa;
        long long sum=0;
        long long sout=0;
        for(int i=0;i<=n+w+w+1;i++)
        {
            sums[i]=sumout[i]=0;
        }

        mins=1234567891234;
        for(int i=w;i<w+n;i++)
         {
             scanf("%d",&aa);
             if(aa>h)
                sout=sout+aa-h;

            sumout[i]=sout;
             sum=sum+aa;
             sums[i]=sum;
         }
         for(int i=n+w;i<=n+w+w+1;i++)  //注意一下后面的sum也要更新
         {
             sums[i]=sums[i-1];
             sumout[i]=sumout[i-1];
         }
         if(sum<w*h)
         {
             printf("-1\n");
             continue;
         }
         for(int i=1;i<=n+w-1;i++)
         {

             int tt=i+w-1;
             int ss=i-1;
            long long allout=sumout[tt]-sumout[ss];
             long long allsum=sums[tt]-sums[ss];
             if(allsum>=w*h)
             {
                 if(allout<mins)mins=allout;
             }
             else
             {
                 if(allout+w*h-allsum<mins)mins=allout+w*h-allsum;
             }
         }
        printf("%I64d\n",mins);
    }
    return 0;
}

hdu5191

原文：http://blog.csdn.net/u011498819/article/details/44536399