0948-令牌放置

你的初始能量为 power，初始分数为 0，只有一包令牌 tokens 。其中 tokens[i] 是第 i
个令牌的值（下标从 0 开始）。

令牌可能的两种使用方法如下：

如果你至少有 token[i] 点能量，可以将令牌 i 置为正面朝上，失去 token[i] 点能量，并得到 1 分。
如果我们至少有 1 分，可以将令牌 i 置为反面朝上，获得 token[i] 点能量，并失去 1 分。

每个令牌最多只能使用一次，使用 顺序不限 ，不需使用所有令牌。

在使用任意数量的令牌后，返回我们可以得到的最大分数。

示例 1：

**输入：** tokens = [100], power = 50
**输出：** 0
**解释：** 无法使用唯一的令牌，因为能量和分数都太少了。

示例 2：

**输入：** tokens = [100,200], power = 150
**输出：** 1
**解释：** 令牌 0 正面朝上，能量变为 50，分数变为 1 。
不必使用令牌 1 ，因为你无法使用它来提高分数。

示例 3：

**输入：** tokens = [100,200,300,400], power = 200
**输出：** 2
**解释：** 按下面顺序使用令牌可以得到 2 分：
1. 令牌 0 正面朝上，能量变为 100 ，分数变为 1
2. 令牌 3 正面朝下，能量变为 500 ，分数变为 0
3. 令牌 1 正面朝上，能量变为 300 ，分数变为 1
4. 令牌 2 正面朝上，能量变为 0 ，分数变为 2

提示：

0 <= tokens.length <= 1000
0 <= tokens[i], power < 104

方法一：贪心

思路

如果让我们来玩令牌放置这个游戏，在让令牌正面朝上的时候，肯定要去找能量最小的令牌。同样的，在让令牌反面朝上的时候，肯定要去找能量最大的令牌。

算法

只要还有能量，就一直让令牌正面朝上，直到没有能量的时候，让一个令牌反面朝上从而获得能量继续之前的操作。

一定要小心处理边界条件，不然很有可能会写出错误的答案。这里要牢牢记住，在有能量时候，只能让令牌正面朝上，直到能量不够用了才能让令牌反面朝上。

最终答案一定是在一次让令牌正常朝上操作之后产生的（永远不可能在让令牌反面朝上操作之后产生）

[solution1-Java]class Solution {
    public int bagOfTokensScore(int[] tokens, int P) {
        Arrays.sort(tokens);
        int lo = 0, hi = tokens.length - 1;
        int points = 0, ans = 0;
        while (lo <= hi && (P >= tokens[lo] || points > 0)) {
            while (lo <= hi && P >= tokens[lo]) {
                P -= tokens[lo++];
                points++;
            }

            ans = Math.max(ans, points);
            if (lo <= hi && points > 0) {
                P += tokens[hi--];
                points--;
            }
        }

        return ans;
    }
}

[solution1-Python]class Solution(object):
    def bagOfTokensScore(self, tokens, P):
        tokens.sort()
        deque = collections.deque(tokens)
        ans = bns = 0
        while deque and (P >= deque[0] or bns):
            while deque and P >= deque[0]:
                P -= deque.popleft()
                bns += 1
            ans = max(ans, bns)

            if deque and bns:
                P += deque.pop()
                bns -= 1

        return ans

复杂度分析

时间复杂度： O(N \log N)，其中 N 是 tokens 的大小。
空间复杂度： O(N)。

0948-令牌放置

方法一： 贪心

方法一：贪心