# 資訊

:::info
- Question: 948. Bag of Tokens
- From: Leetcode Daily Challenge 2024.03.04
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

You start with an initial power of `power`, an initial `score` of 0, and a bag of tokens given as an integer array `tokens`, where each `tokens[i]` donates the value of token$_i$.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

1. **Face-up**: If your current power is at least `tokens[i]`, you may play token$_i$, losing `tokens[i]` power and gaining `1` score.
2. **Face-down**: If your current `score` is at least `1`, you may play token$_i$, gaining `tokens[i]` power and losing `1` score.

Return the maximum possible score you can achieve after playing any number of tokens.

> Example 1:
:::success
- Input: `tokens = [100]`, `power = 50`
- Output: 0
- Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than `tokens[0]` (100).
:::

> Example 2:
:::success
- Input: `tokens = [200,100]`, `power = 150`
- Output: 1
- Explanation:
- Play token$_1$ (100) face-up, reducing your power to 50 and increasing your score to 1.
- There is no need to play token$_0$, since you cannot play it face-up to add to your score. The maximum score achievable is 1.
:::

> Example 3:
:::success
- Input: tokens = [100,200,300,400], power = 200
- Output: 2
- Explanation: Play the tokens in this order to get a score of 2:
- Play token$_0$ (100) face-up, reducing power to 100 and increasing score to 1.
- Play token$_3$ (400) face-down, increasing power to 500 and reducing score to 0.
- Play token$_1$ (200) face-up, reducing power to 300 and increasing score to 1.
- Play token$_2$ (300) face-up, reducing power to 0 and increasing score to 2.
- The maximum score achievable is 2.
:::

> Constraints:
:::success
- 0 <= `tokens.length` <= 1000
- 0 <= `tokens[i]`, `power` < $10^4$
:::

---

# 解法

## 概念

這題概念是這樣：如果我有絕對足夠的 power，就全部拿來兌換 score，如果沒有就拿來兌換 power，唯一一個小細節要注意就是最後可能會出現一些兌換 power 但沒用到的「多扣掉」的那些 score，需要記憶起來，最後把他加回去，畢竟目標是最大的 score 而不是 power。

所以這題我會對 tokens 做 sorting，要兌換 score 就一定是從最小的開始兌換，因為可以花比較少錢買到 score，而如果要兌換 power 就要從最大的開始兌換，才是最划算的，所以可以看到在經過 sorting 之後最左邊會是我希望兌換 score 的 tokens，而最右邊是我希望兌換 power 的 tokens，這時候就可以透過 two pointers 做到我想做的事情。

最後有個地方要注意：第一段提到多扣掉的 score 在我的程式中是使用 bag 這個變數暫存

## 程式碼

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        l = 0
        r = len( tokens ) - 1
        score = 0
        tokens.sort()
        bag = 0
        while l <= r:
            if power >= tokens[l]:
                score += 1
                power -= tokens[l]
                l += 1
                bag = 0
            elif score > 0:
                score -= 1
                power += tokens[r]
                r -= 1
                bag += 1
            else:
                break
        return score + bag

---

# 複雜度

## 時間複雜度

會走完一次 list，所以是 $O(n)$


## 空間複雜度

空間部分只有三個變數，所以是 $O(1)$