Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1585070
  • 博文数量: 399
  • 博客积分: 8508
  • 博客等级: 中将
  • 技术积分: 5302
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-14 09:28
个人简介

能力强的人善于解决问题,有智慧的人善于绕过问题。 区别很微妙,小心谨慎做后者。

文章分类

全部博文(399)

文章存档

2018年(3)

2017年(1)

2016年(1)

2015年(69)

2013年(14)

2012年(17)

2011年(12)

2010年(189)

2009年(93)

分类: LINUX

2009-12-24 11:35:49

#include
#include
enum{M=30001};
bool ind[M];
int n;
// 20*|j-i| +10*num + (j-1)*4<=t  ,这是电梯停在j层时,任何一个人到达i层所需的时间所要满足的不等式
int solve(int t) //规定时间t内所有人是否都能到达目标层
{
    int i,j,now=0,num=0;
    i=t/20+2;   //i层以下的人直接走楼梯
    while(i<=n)
    {
        while(i<=n && ind[i]==false) //i层没人时不用理,即找到要停的第一层
            i++;   
        //ind[i]=true;
        if((i-1)*4+10*num>t) //电梯无法在时间t之内到达i层,因为t已经小于到达i层时间的下界了
            return 0;  
        j=(t-10*num+20*i+4)/24; //电梯在第j层停靠最好,利用t时间范围内电梯在j停,某人向下走到i,尽量向上,此时j>i
        i=(t-10*num+16*j+4)/20+1;//电梯i层以下的都已经搞定,利用t时间范围内电梯在j停,向上能到达最大层i,之后直接升到i层上面,此时i>j;  这样会使电梯停的次数最小,体现了贪心算法
        num++;
    }
    return 1;
}
main()
{
    int i,j,min,max,mid,t;
    //freopen("data.txt","r",stdin)
    while(1)
    {
        scanf("%d",&t);
        if(t==0)
            break;
        memset(ind,false,sizeof(ind));
        n=-1;   //读入数据
        for(i=0;i        {
            scanf("%d",&j);
            if(j>n)
                n=j;
            ind[j]=true;
        }
        //二分法,查找区间为[min,max],其中min总是不可行的,max则为可行解
        min=0;max=14*(n-1);
        while(min        {
            mid=(min+max)/2;
            if(solve(mid)==1)
                max=mid;
            else
                min=mid;
        }
        printf("%d\n",max);
    }
    return 0;
阅读(886) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~