出租车换乘问题 - 详细题解

题目重述

Bajtazar 要从起点（Bajtodziura）前往终点（Bajtodół），总距离为 m 公里。在距离起点 d 公里处有一个出租车基地，拥有 n 辆出租车。每辆出租车 i 最多能行驶 x[i] 公里。

规则：

• 可以中途换乘出租车
• 所有出租车都从基地出发
• 出租车不需要返回基地
• 求最少需要多少辆出租车才能到达终点，如果无法到达输出 0

问题分析

关键观察

1. 基地位置重要性：所有出租车都从基地出发，所以我们需要：

   • 先用一些车把乘客从起点送到基地（前 d 公里）
   • 然后用车辆从基地向终点推进（后 m-d 公里）

2. 车辆有效性：一辆车要能发挥作用，必须：

   • 能开到当前位置（如果当前位置在基地之前）
   • 能推进一定的距离

3. 最优策略：贪心地选择能推进最远的车辆

算法思路

步骤1：预处理

sort(x + 1, x + n + 1);  // 将出租车按行驶距离排序

步骤2：可行性检查

必须至少有一辆车能覆盖从基地到终点的距离：

if (x[n] < m - d) {
    puts("0");  // 没有车能完成最后一段路程
    exit(0);
}

步骤3：找到关键车辆

找到第一辆能覆盖 m-d 距离的车：

p = lower_bound(x + 1, x + n + 1, m - d) - x;

步骤4：贪心推进

从最远的车开始考虑：

for (int i = n; i >= 1; i--) {
    // 检查当前车是否能直接完成剩余路程
    if (m + d - 2 * now <= x[i]) {
        // 可以一次性到达
    }
    
    // 跳过关键车辆（留作最后使用）
    if (i == p) continue;
    
    // 检查车辆是否能到达当前位置
    if (x[i] <= d - now) {
        // 车辆无法到达当前位置，失败
    }
    
    // 使用这辆车，更新位置
    ans++;
    now += x[i] - d + now;
}

核心公式解释

1. 推进距离计算

当在位置 now 使用一辆能行驶 x 公里的车时：

• 需要先开到基地：距离 d - now
• 剩余油量：x - (d - now)
• 能推进的距离：x - (d - now)
• 新位置：now + [x - (d - now)] = x - d + 2*now

2. 直接完成条件

一辆车能直接完成剩余路程的条件：

m + d - 2 * now <= x[i]

解释：

• 需要从当前位置开到基地：d - now
• 再从基地开到终点：m - d
• 总需要：(d - now) + (m - d) = m - now
• 但由于车从基地出发，实际需要：m + d - 2 * now

完整算法流程

1. 排序：将所有出租车按行驶距离从小到大排序
2. 可行性检查：检查是否有车能覆盖 m-d 距离
3. 初始化：now = 0（当前位置），ans = 0（已用车辆数）
4. 贪心选择：
   • 从最好的车（行驶距离最长）开始考虑
   • 如果当前车能直接完成旅程，使用它并结束
   • 否则，使用能推进最远的可用车辆
   • 更新当前位置和车辆计数
5. 最终检查：如果成功到达，输出车辆数；否则输出0

代码实现详解

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5;
int m, d, n, p;
int x[N];

signed main() {
    cin >> m >> d >> n;
    for (int i = 1; i <= n; i++) cin >> x[i];
    
    // 步骤1：排序
    sort(x + 1, x + n + 1);
    
    // 步骤2：可行性检查
    if (x[n] < m - d) {
        cout << 0 << endl;
        return 0;
    }
    
    // 步骤3：找到关键车辆
    p = lower_bound(x + 1, x + n + 1, m - d) - x;
    int now = 0, ans = 0;
    
    // 步骤4：贪心推进
    for (int i = n; i >= 1; i--) {
        // 检查是否能直接完成
        if (m + d - 2 * now <= x[i]) {
            cout << ans + 1 << endl;
            return 0;
        }
        
        // 跳过留作最后使用的关键车辆
        if (i == p) continue;
        
        // 检查车辆是否能到达当前位置
        if (x[i] <= d - now) {
            cout << 0 << endl;
            return 0;
        }
        
        // 使用这辆车
        ans++;
        now += x[i] - d + now;  // 更新位置
        
        // 检查是否已到达终点
        if (now >= m) {
            cout << ans << endl;
            return 0;
        }
        
        // 检查是否已过基地
        if (now >= d) break;
        
        // 检查关键车辆是否能完成剩余路程
        if (x[p] >= m + d - 2 * now) {
            cout << ans + 1 << endl;
            return 0;
        }
    }
    
    // 步骤5：最终处理
    if (now < d) {
        cout << 0 << endl;
    } else {
        cout << ans + 1 << endl;
    }
    
    return 0;
}

样例分析

输入：

42 23 6
20 25 14 27 30 7

处理过程：

1. 排序后：7, 14, 20, 25, 27, 30
2. 关键车辆：能覆盖 42-23=19 公里的第一辆车是 20
3. 贪心选择：
   • 使用 30：推进到 30-23+0=7 公里
   • 使用 27：推进到 27-23+14=18 公里
   • 使用 25：推进到 25-23+36=38 公里
   • 使用关键车辆 20 完成最后一段

总计使用4辆车。

学习要点

1. 贪心证明：为什么选择能推进最远的车是最优的？
2. 位置更新公式：理解 now += x[i] - d + now 的推导
3. 边界处理：各种特殊情况的条件判断
4. 算法优化：通过排序和二分查找提高效率

这个问题的核心在于将复杂的换乘问题转化为贪心的位置推进问题，通过巧妙的公式计算每次能推进的距离。