题意分析

ZSoft公司所在的高科大厦门楼只有一部电梯，但有数百个公司，导致员工每天早上等电梯浪费大量时间。为了提高电梯运行效率，需要设计一个最优的停靠方案，使得最后一个到达目标楼层的人的时间最小化。

关键条件：

• 电梯上升一层需要4秒
• 电梯每停靠一次需要额外停留10秒
• 乘客可以选择在任意楼层下电梯，然后步行到达目标楼层，步行一层需要20秒
• 目标是设计一个电梯停靠方案，使得最后一个到达目标楼层的人的时间尽可能短

解题思路

这是一个典型的最优化问题，可以使用二分查找来解决。基本思路是：

1. 二分查找最小时间：确定一个可能的时间范围，通过二分查找找到满足条件的最小时间
2. 验证函数：对于每个候选时间，验证是否存在一个停靠方案，使得所有乘客都能在这个时间内到达目标楼层
3. 贪心策略：在验证过程中，使用贪心策略确定电梯的最优停靠点，尽可能覆盖更多的目标楼层

具体步骤：

1. 确定二分查找范围：下界是电梯直达最高层的时间，上界是所有人都步行的时间
2. 二分查找：对于每个中间时间mid，检查是否可以通过合理的停靠方案使所有乘客在mid时间内到达
3. 验证函数：从第一层开始，尽可能选择最远的停靠点，使得该停靠点覆盖的所有楼层的乘客都能在mid时间内到达

标准程序

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

bool check(const vector<int>& floors, int time) {
    int current_floor = 1;
    int current_time = 0;
    bool stopped = false;

    for (int target : floors) {
        if ((target - current_floor) * 20 + current_time > time) {
            if (stopped) {
                current_time += 10;
                if (current_time > time) return false;
            }

            int elevator_time = (target - current_floor) * 4;
            if (current_time + elevator_time > time) return false;

            int k = target;
            while (k <= 30000) {
                int elevator_time_k = (k - current_floor) * 4;
                int walk_time = (k - target) * 20;
                int total_time = current_time + elevator_time_k + walk_time;

                if (total_time > time) break;
                k++;
            }
            k--;

            current_time += (k - current_floor) * 4;
            current_floor = k;
            stopped = true;
        }
    }

    return true;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        vector<int> floors(n);
        for (int i = 0; i < n; i++) {
            cin >> floors[i];
        }

        int left = (floors[0] - 1) * 4 - 1;
        int right = (floors.back() - 1) * 20;

        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            if (check(floors, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }

        cout << right << endl;
    }

    return 0;
}

代码解释

二分查找部分：

• left初始化为电梯直达最低目标楼层的时间减1
• right初始化为所有人都步行到最高目标楼层的时间
• 在每次二分查找中，检查中间值mid是否满足条件，调整上下界

验证函数check：

• 从第一层开始模拟电梯运行
• 对于每个目标楼层，如果步行时间超过当前候选时间time，则需要电梯停靠
• 停靠时，选择最远的可能楼层，使得该楼层及之前的楼层都能在time内到达
• 更新电梯位置和时间，继续处理后续楼层

这个算法通过二分查找和贪心策略，高效地找到了最优解，时间复杂度为O(n log m)，其中n是目标楼层数，m是时间范围。