贪心法求解电梯问题

djkpengjun

                #include
#include
enum{M=30001};
bool ind[M];
int n;
// 20*|j-i| +10*num + (j-1)*4t) //电梯无法在时间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;in)
                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;
}
               
               
               
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/104733/showart_2129517.html