# 2073. Time Needed to Buy Tickets Leetcode [C/C++/python]

## 敘述
There are n people in a line queuing to buy tickets, where the 0th person is at the front of the line and the (n - 1)th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the ith person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k (0-indexed) to finish buying tickets.

### Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

### Constraints:

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

## 暴力法

int timeRequiredToBuy(int* tickets, int ticketsSize, int k) {
    int count = 0;
    while (tickets[k]) {
        for (int i = 0; i < ticketsSize; i++) {
            if (tickets[i]) {
                tickets[i]--;
                count++;
            }
            if (!tickets[k])
                break;
        }
    }
    return count;
}

worst case : $O(n^2)$
因為 tickets[i] <= 100，算作為常數，所以這邊 $O(n^2)$，其實是 $O(n)$，所以暴力法就可以到 beats 100% 了。
隨然依照算法有更快的方法，但是我看到這題的限制敘述他的陣列長度 <=100 ，所以此情況使用暴力法會是與 $O(n)$ 方法差不多。

## $O(n)$ 方法

int timeRequiredToBuy(int* tickets, int ticketsSize, int k) {
    int count = 0;
    int tmp = tickets[k];
    for (int i = 0; i <= k; i++) {
        if (tickets[i] < tmp)
            count += tickets[i];
        else
            count += tmp;
    }
    for (int i = k + 1; i < ticketsSize; i++) {
        if (tickets[i] < tmp - 1)
            count += tickets[i];
        else
            count += tmp - 1;
    }
    return count;
}

此方法只需要遍歷陣列一次就好，所以時間複雜度會保持在 $O(n)$，雖然在這題因為測試項目的限制所以沒有發揮優勢，但是保持進步！

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        target = tickets[k]
        time = 0
        for i in tickets[:k]:
            if i < target:
                time += i
            else:
                time += target
        for i in tickets[k:]:
            if i < target:
                time += i
            else:
                time += target - 1
        return time + 1

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