#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;
}
阅读(874) | 评论(0) | 转发(0) |