自动搬运

查看原文

来自洛谷，原作者为

	Kingsley1116 「愛七色五味多紛陳 更多灰塵 落入五蘊」

搬运于2025-08-24 21:50:05，当前版本为作者最后更新于2025-08-17 14:30:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

題目描述

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;
}