首页 > Windows开发 > 详细

bc#34-2 Building Blocks

时间:2015-03-23 00:20:50      阅读:256      评论:0      收藏:0      [点我收藏+]

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=572&pid=1002

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

1.枚举求出每w堆需要最少移动的积木数,max(高变矮需要的数目,矮变高需要的数目),在求出最小值

2.需要输入优化

3.最终选取的W堆积木中,有可能有几堆原本不存在。如 9 8 7 形成3*3,可把3堆积木变成5堆 3 3 3 8 7,最少移动6个积木。因此需要在n堆积木两端补上W个0。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define maxn 50050
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
ll n,w,h;
ll a[maxn*3];
bool check()
{
    ll sum=0;
    for(int i=w;i<n+w;i++)sum+=a[i];
    return sum>=w*h?true:false;
}
int getint() {
    int ret=0;bool ok=0,neg=0;
    for(;;) {
        int c=getchar();
        if(c>=0&&c<=9)ret=(ret<<3)+ret+ret+c-0,ok=1;
        else if(ok)return neg?-ret:ret;
        else if(c==-)neg=1;
    }
}
int main()
{

    while(~scanf("%d%d%d",&n,&w,&h))
    {
        for(int i=0;i<w;i++)a[i]=0;
        for(int i=w;i<n+w;i++)a[i]=getint();
        for(int i=n+w;i<n+2*w;i++)a[i]=0;
        if(check()==false){
            puts("-1");
            continue;
        }
        ll positive=0,negative=0,mi;
        for(int i=0;i<w;i++)a[i]>h?positive+=a[i]-h:negative+=h-a[i];
        mi=max(positive,negative);
        for(int i=w;i<n+2*w;i++)
        {
            a[i]>h?positive+=a[i]-h:negative+=h-a[i];
            a[i-w]>h?positive-=a[i-w]-h:negative-=h-a[i-w];
            ll tmp=max(positive,negative);
            mi=min(mi,tmp);
        }
        printf("%lld\n",mi);
    }
    return 0;
}

/*
3 3 3
9 8 7
*/

 

bc#34-2 Building Blocks

原文:http://www.cnblogs.com/kylehz/p/4358352.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!