2073. Time Needed to Buy Tickets

📘 題目敘述

有 n 個人排成一列買票，第 0 個人在最前面，第 (n - 1) 個人在最後面。

給你一個 0-indexed 陣列 tickets，其中 tickets[i] 表示第 i 個人總共想買幾張票。

每個人每次買一張票剛好花 1 秒。 如果某個人還有票要買，他買完一張後會立刻回到隊伍最後面；如果他已經不需要再買票，就會直接離開隊伍。

請回傳原本在位置 k 的那個人，完成買票總共需要多少時間。

條件限制

• n == tickets.length
• 1 <= n <= 100
• 1 <= tickets[i] <= 100
• 0 <= k < n

🧠 解題思路

這題我沒有真的模擬整個 queue 的移動，而是直接去想：

• 在第 k 個人買完之前
• 每個人最多會買幾次票

關鍵在於 tickets[k]。

因為第 k 個人總共要買 tickets[k] 張，所以在他結束之前：

• 在 k 前面或剛好是 k 的人，最多都可能買到 tickets[k] 次
• 在 k 後面的人，因為當第 k 個人買完最後一張時流程就停止了，所以他們最多只可能買到 tickets[k] - 1 次

接著每個人真正貢獻多少秒，就看：

• 他本來想買幾張
• 和他在第 k 個人結束前最多有機會買幾次

兩者取最小值就可以。

所以這題的核心就是：

不用真的模擬排隊，只要分成 i <= k 和 i > k 兩段，算每個人在第 k 個人結束前最多能買幾次票，再把這些次數加總起來。

所有變數

• n：陣列長度
• t：總時間，也就是最後答案

🪜 主要流程步驟

1. 先取得人數，並準備答案變數

這裡：

• n 是總共有幾個人
• t 用來累加總共花掉的秒數

因為每買一張票就是 1 秒，所以最後其實就是把每個人在第 k 個人完成之前買到的票數加總起來。

2. 枚舉每一個人，計算他對答案的貢獻

for (int i = 0; i < n; i++) {

我現在要看每個人 i，在第 k 個人完成買票之前，最多會買幾張票。

每個人的貢獻都算完後，加總起來就是總時間。

3. 如果這個人在 k 的前面或就是 k，他最多能買到 tickets[k] 次

if (i <= k) {
    t += min(tickets[k], tickets[i]);
}

這裡的原因是：

• 第 k 個人會真的買到第 tickets[k] 張才結束
• 所以在他之前的那些人，包含他自己，都有機會參與到第 tickets[k] 輪

但某個人自己可能本來就只想買更少張， 所以他真正能買幾次，要取：

• tickets[k]
• tickets[i]

兩者較小值

也就是：

min(tickets[k], tickets[i])

4. 如果這個人在 k 的後面，他最多只能買到 tickets[k] - 1 次

這裡是整題最關鍵的地方。

因為排在 k 後面的人，在第 k 個人買完最後一張票的那一輪裡， 流程會在第 k 個人那裡就停止，所以這些人沒機會再輪到那一輪。

因此他們最多只能參與到前面 tickets[k] - 1 輪。

所以他們真正貢獻的秒數就是：

• tickets[k] - 1
• tickets[i]

取最小值。

5. 為什麼這樣加總就等於總秒數

因為每買一張票就固定花 1 秒， 所以整個過程的總時間，其實就等於：

• 在第 k 個人完成之前
• 所有人總共買了幾張票

而這份程式正是在逐一計算每個人會買幾張票，最後把它們全部加總起來。

所以不需要真的用 queue 模擬整個輪轉，也能直接得到答案。

6. 最後回傳總時間

當所有人的貢獻都加完後，t 就是第 k 個人完成買票所需的總秒數。

⏱️ 複雜度

設 n = tickets.length。

• 時間複雜度：O(n)
  只掃一次陣列。
• 空間複雜度：O(1)
  只用了固定數量的變數。

💻 程式碼實作

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int n = tickets.size();
        int t = 0;
        for (int i = 0; i < n; i++) {
            if (i <= k) {
                t += min(tickets[k], tickets[i]);
            } else {
                t += min(tickets[k] - 1, tickets[i]);
            }
        }
        return t;
    }
};

🔗 題目連結

https://leetcode.com/problems/time-needed-to-buy-tickets/