題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🌈 AWC0104B Bus Arrival Time

Problem Statement

題目簡述

有 NN 條公車路線會經過同一個站牌。第 ii 條路線的公車會在 0,Ai,2Ai,3Ai,…0,A_i,2A_i,3A_i,\ldots 分鐘時到站。
高橋只想搭乘到站時間不早於 TT 的公車，求所有路線中最早能搭到的到站時間。

Constraints

約束條件

  • 1≤N≤1051 \le N \le 10^5
  • 0≤T≤1090 \le T \le 10^9
  • 1≤Ai≤1091 \le A_i \le 10^9
  • 輸入皆為整數

思路：計算每條路線的下一班車

每條路線的到站時間都是公差固定的倍數序列，所以只要算出這條路線第一個不小於 TT 的倍數即可。

Tip

若班距是 xx，最早不小於 TT 的班次可以寫成

x⋅⌈Tx⌉x \cdot \left\lceil \frac{T}{x} \right\rceil

在整數運算中，⌈Tx⌉\left\lceil \frac{T}{x} \right\rceil 可用 T+x−1x\frac{T+x-1}{x} 的整除形式計算。

把每條路線各自算出的候選到站時間取最小值，就是答案。若 T=0T=0，所有路線在時間 00 都有車，因此公式也會自然得到 00。

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
  • 空間複雜度：O(1)\mathcal{O}(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from math import inf


def solve():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == N

    ans = inf
    for x in A:
        m = (T + x - 1) // x  # ceil(T / x)
        ans = min(ans, x * m)
    print(ans)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @Rosuuri. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.