解題說明
Time Needed to Buy Tickets
題目描述: 有 n 個人排隊買票,第 i 個人要買 tickets[i] 張票。每個人每次只能買一張,買完後回到隊尾。若某人買完所有需要的票就離開。求第 k 個人買完所有票需要多少秒。
解題思路: 不需要真的模擬排隊過程,可以直接計算每個人對總時間的貢獻。
- 設目標人第 k 個人需要買 tickets[k] 張票。
- 對於排在 k 前面或等於 k 的人(i <= k):他們每輪都比 k 先買到票。他們的貢獻為 min(tickets[i], tickets[k])。
- 對於排在 k 後面的人(i > k):在 k 買完最後一張票的那一輪,他們還沒輪到。所以他們的貢獻為 min(tickets[i], tickets[k] - 1)。
- 總時間 = 所有人的貢獻之和。
C++ 解法
複雜度分析
時間複雜度:O(n) — 遍歷一次陣列即可計算答案。
空間複雜度:O(1) — 只使用常數額外空間。
虛擬碼
1. Initialize time = 0. 2. For each person i from 0 to n-1: a. If i <= k: time += min(tickets[i], tickets[k]). b. If i > k: time += min(tickets[i], tickets[k] - 1). 3. Return time.
其他解法
-
直接模擬法:使用佇列模擬排隊過程,每次從隊頭取一人、買一張票、若未買完則回到隊尾。當第 k 個人買完時回傳時間。時間複雜度 O(n * max(tickets[i])),對於大量票數時效率低。
-
分層計算法:按輪次計算,每一輪所有還在隊列中的人各買一張。追蹤每輪離開的人數。本質上等價於上面的 O(n) 解法,但分層思考可能更直觀。
延伸思考
- 若每個人每次可以買最多 M 張票(而非固定 1 張),總時間如何計算?
- 若有 VIP 通道,部分人可以插隊,如何修改計算方式?
- 若有多個售票窗口同時服務,且每個人會選擇最短的隊列,問題會如何變化?