当前位置: 首页 >> 程序设计 >> 数据结构和算法 >> 贪心法求解电梯问题

贪心法求解电梯问题

作者：bpsub 来源：zz 发表时间：2009-12-29 浏览次数：字号：大 中 小

内容摘要 algorithm

中国源码网内相关主题链接

#include <cstdio>
#include <string>
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<t;i++)
        {
            scanf("%d",&j);
            if(j>n)
                n=j;
            ind[j]=true;
        }
        //二分法，查找区间为[min,max],其中min总是不可行的，max则为可行解
        min=0;max=14*(n-1);
        while(min<max-1)
        {
            mid=(min+max)/2;
            if(solve(mid)==1)
                max=mid;
            else
                min=mid;
        }
        printf("%d\n",max);
    }
    return 0;
}