# 資訊

:::info
- Question: 2073. Time Needed to Buy Tickets
- From: Leetcode Daily Challenge 2024.04.09
- Difficulty: Easy
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

There are `n` people in a line queuing to buy tickets, where the $0^{th}$ 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 $i^{th}$ 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:
:::success
* 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.
:::

> Example 2:
:::success
* Input: `tickets = [5,1,1,1]`, `k = 0`
* Output: 8
* Explanation:
* In the first pass, everyone in the line buys a ticket and the line becomes `[4, 0, 0, 0]`.
* In the next 4 passes, only the person in position 0 is buying tickets.
* The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.
:::

> Constraints:
:::success
* `n` == `tickets.length`
* 1 <= `n` <= 100
* 1 <= `tickets[i]` <= 100
* 0 <= `k` < `n`
:::

---

# 解法

## 概念

這題雖然說 queue，但個人覺得 simulation 的成分比較多，counting 可能更是重點

這題我以 `k` 作為一個分界，在 `k` 之前的如果比 `tickets[k]` 多，他也買不到，因為我們不考慮 `k` 以後的情況，而 `k` 之後的最多只能走到 `tickets[k] - 1` 那麼多，所以在寫 `min` 的時候要記得處理這種情況

## 程式碼

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        ans = 0
        for i in range(k):
            ans += min( tickets[i], tickets[k] )
        ans += tickets[k]
        for i in range(k+1,len(tickets)):
            ans += min( tickets[i], tickets[k]-1 )
        return ans

---

# 複雜度

## 時間複雜度

Simply $O(n)$


## 空間複雜度

Simply $O(1)$