2073. 買票需要的時間

思路

答案至少會是 tickets[k]，事先計入答案。

按照題目模擬，首先前面的人會買下第一張票。
接下來第 k 個人買票，買了之後檢查是否歸零，
如果歸零，他就不用排隊了，如果沒歸零，必然要再等待完整一輪排隊，
後面的人買下第一張票，並檢查是否需要繼續買票，並利用模運算去處理第二輪的前 k 個人。

第二個方法是直接計算， 在第 k 個人買最後一張票時，假設是 $5$，

• 排在前面的人買的票不會超過五張，
• 排在後面的不會超過四張， 所以把每個人想買的票數跟 $5$ 和 $4$ 各取最小值後相加，就是答案。

程式碼

1. 模擬

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int n = tickets.size();
        int res = tickets[k];
        for(int i = 0; i < k; ++i) { // 排在前面的人買第一張票
            tickets[i]--;
            res++;
        }
        while(--tickets[k] > 0) {
            for(int i = 1; i < n; ++i) { // 後面的人，以及下一輪的前 k 個人購買票
                if(tickets[(i + k) % n] == 0) {
                    continue;
                }
                tickets[(i + k) % n]--;
                ++res;
            }
        }
        return res;
    }
};

2. 直接計算

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

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$