P3550 [POI 2013] TAK-Taxis 題解

· · 题解

題目描述

Byteasar 想要從 Bytehole 鎮乘坐計程車前往 Bytepit 鎮，兩地之間的距離為 m 公里。在路途中，距離 Bytehole 鎮恰好 d 公里處有一個計程車基地，基地中有 n 輛計程車，每輛計程車的燃料恰好可行駛 x_i 公里。

Byteasar 可以在任意地點換乘計程車，且所有計程車都從基地出發（無需返回基地）。任務是判斷 Byteasar 能否從 Bytehole 抵達 Bytepit，若可以，則求出所需的最少計程車數量；若不可，則輸出 0。

輸入格式：
第一行包含三個整數 m, d, n（1 \le d \le m \le 10^{18}，1 \le n \le 500\,000），分別表示總距離、基地位置、計程車數量。
第二行包含 n 個整數 x_1, x_2, \cdots, x_n，表示每輛計程車的最大行駛距離。

輸出格式：
輸出最少計程車數量，若無法抵達則輸出 0。

思路

要完成旅程，需滿足兩個核心條件：

  1. 至少有一輛計程車能從基地抵達終點（即行駛距離 \ge 基地到終點的距離 m-d）。
  2. 能通過換乘計程車，從起點（0 公里）抵達某個位置，使得最後一輛計程車能從基地出發，接載 Byteasar 並抵達終點。

具體步驟

  1. 特殊情況判斷：單輛計程車直達
    若存在一輛計程車的行駛距離 \ge d + m，則它可從基地出發，先開到起點（距離 d），再直接開到終點（距離 m），此時只需 1 輛計程車。

  2. 篩選能抵達終點的計程車
    基地到終點的距離為 m-d，因此需至少有一輛計程車的 x_i \ge m-d（否則直接輸出 0）。
    將計程車按行駛距離降序排序後，篩選出所有滿足 x_i \ge m-d 的計程車，選取其中最強的一輛（即排序後的第一輛）作為「最後一輛」負責抵達終點。

  3. 貪心擴展覆蓋範圍
    剩餘的計程車需用於覆蓋從起點到基地附近的距離。目標是通過換乘，讓 Byteasar 能抵達盡可能遠的位置（記為 current），從而減少最後一輛計程車的負擔。

    • 每次選擇剩餘計程車中行駛距離最長的，計算其能擴展的覆蓋範圍：current 更新為 2 \times current + (x_i - d) 。
    • 若某次選擇的計程車無法擴展覆蓋範圍（x_i \le d - current），則無法抵達，輸出 0。

  4. 最終驗證
    判斷最後一輛計程車能否覆蓋剩餘距離：需滿足 m + d - 2 \times current \le x_{last}（其中 x_{last} 是最後一輛計程車的行駛距離）。若滿足，則總計程車數量為「擴展用計程車數 + 1（最後一輛）」；否則輸出 0。

代碼實現

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    long long m, d, n;
    cin >> m >> d >> n;
    vector<long long> a(n);
    for (long long i = 0; i < n; i++) cin >> a[i];
    sort(a.rbegin(), a.rend());

    if (a[0] >= m + d) {
        cout << 1;
        return 0;
    }

    long long pointer = 0;
    for (; pointer < n; pointer++) {
        if (a[pointer] < m - d) break;
    }
    pointer--;
    if (pointer < 0) {
        cout << 0;
        return 0;
    }
    long long ans = 0, current = 0;
    for (long long i = 0; i < n; i++) {
        if (i == pointer) continue;
        if (current >= d || m + d - 2 * current <= a[pointer]) break;
        if (a[i] <= d - current) {
            cout << 0;
            return 0;
        }
        ans++;
        current += a[i] - d + current;
        if (current >= m) {
            ans--;
            break;
        }
    }

    cout << ((m + d - 2 * current > a[pointer]) ? 0 : ans + 1);
    return 0;
}