ZeroJudge 解題筆記：t165.末班公車

作者：王一哲
日期：2026年11月2日


ZeroJudge 題目連結：t165.末班公車

解題想法

每組測資第一列為兩個整數 $n ~(1 \leq n \leq 2 \times 10^5), t ~(0 \leq t \leq 10^9)$，代表有 $n$ 班公車，人抵達公車站的時刻為 $t$；第二列有 $n$ 個整數 $d_i ~(0 \leq d_i \leq 10^9)$，分別代表第 $i$ 班公車發車時刻。印出最短的等車時間，如果沒有車能搭則印出 $-1$。

這題如果知道內建的排序及二分搜工具寫起來很快。先將發車時刻存入陣列 $ds$，將 $ds$ 由小到大排序。再用 Python 的 bisect_left 或是 C++ 的 lower_bound 從 $ds$ 找第一個大於、等於 $t$ 的索引值 $idx$，如果 $idx == n$ 代表找不到，印出 $-1$；反之，印出 $t - ds[idx]$。

Python 程式碼

使用時間約為 11 ms，記憶體約為 9.4 MB，通過測試。

def solve():
    import sys
    from bisect import bisect_left

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        t = int(data[ptr + 1])
        ptr += 2
        ds = sorted(map(int, data[ptr : ptr + n]))
        ptr += n
        idx = bisect_left(ds, t)
        if idx == n:
            result.append("-1\n")
        else:
            result.append(f"{ds[idx] - t:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 16 ms，記憶體約為 9.6 MB，通過測試。

from bisect import bisect_left

while True:
    try:
        n, t = map(int, input().split())
        ds = sorted(map(int, input().split()))
    except EOFError:
        break
    
    idx = bisect_left(ds, t)
    print(-1 if idx == n else ds[idx] - t)

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.6 MB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, t;
    while(cin >> n >> t) {
        vector<int> ds (n);
        for(int i = 0; i < n; i++) {
            cin >> ds[i];
        }
        // ds 排序後用二分搜從中找第一個大於、等於 t 的數值索引值
        sort(ds.begin(), ds.end());
        int idx = lower_bound(ds.begin(), ds.end(), t) - ds.begin();
        if (idx == n) {
            cout << "-1\n";
        } else {
            cout << ds[idx] - t << "\n";
        }
    }
    return 0;
}