解题思路

题目要求为电梯设计最优停靠方案，使得最后一个到达目标楼层的人的时间最短。解题的关键在于找到一种停靠策略，平衡电梯运行时间和乘客步行时间。

方法思路

1. 二分查找最优时间：通过二分查找确定最小的最大到达时间。初始时，左端点设为0，右端点设为一个足够大的值（如30000*20+1）。
2. 贪心验证停靠方案：对于每个中间时间值，使用贪心策略验证是否存在一种停靠方案，使得所有乘客的到达时间都不超过该中间值。
3. 确定停靠楼层：从第一层开始，尽可能选择最远的楼层停靠，确保步行时间和电梯运行时间之和不超过当前验证的时间。

解决代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int da[30010];
int n;
int cnt; 
int tmp[30010];
int sc[30010];

bool check(int time)
{
    int ttt=0;
    int t=0;
    int flag=0;
    int now=1;
    for(int i=0;i<n;i++)
    {
        if((da[i]-now)*20+t>time)
        {
            if(flag==1)
            {
                t=t+10;
            }
            if(t+(da[i]-now)*4>time)
            {
                return false;
            }
            int j;
            for(j=da[i];(j-now)*4+(j-da[i])*20+t<=time;j++);
            j--;
            t=t+(j-now)*4;
            now=j;
            tmp[ttt++]=j;
            flag=1;            
        }
    }
    cnt=ttt;
    for(int i=0;i<cnt;i++)
    {
        sc[i]=tmp[i];
    }
    return true;
}

int main()
{
    while(1)
    {
        scanf("%d",&n);
        if(n==0)
        {
            break;
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d",&da[i]);
        }
        sort(da,da+n);
        int l=0;
        int r=30000*20+1;
        int jg;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))
            {
                r=mid-1;
                jg=mid;
            }else
            {
                l=mid+1;
            }
        }
        cout<<jg<<endl;
        cout<<cnt<<" ";
        for(int i=0;i<cnt;i++)
        {
            cout<<sc[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

代码解释

1. 输入处理：循环读取每个测试用例，直到输入的n为0时结束。
2. 排序：对目标楼层进行排序，确保楼层按升序排列。
3. 二分查找：在时间范围[0, 30000*20+1]内进行二分查找，寻找最小的最大到达时间。
4. 贪心验证函数check：
   • 初始化当前楼层为1，时间为0。
   • 遍历每个目标楼层，如果当前楼层到该目标楼层的步行时间超过当前验证的时间，则需要电梯停靠。
   • 计算最远可以停靠的楼层，使得电梯运行时间和步行时间之和不超过当前验证的时间。
   • 更新当前楼层和时间，记录停靠楼层。
5. 输出结果：二分查找结束后，输出最小的最大到达时间和对应的停靠方案。

这种方法通过二分查找高效地确定最优时间，再利用贪心策略验证并生成停靠方案，确保了算法的时间复杂度和正确性。