难度：★★★☆☆
类型：数组
方法：贪心算法

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

如果你至少有 token[i] 点 能量 ，可以将令牌 i 置为正面朝上，失去 token[i] 点 能量 ，并得到 1 分 。
如果我们至少有 1 分 ，可以将令牌 i 置为反面朝上，获得 token[i] 点 能量 ，并失去 1 分 。
每个令牌 最多 只能使用一次，使用 顺序不限 ，不需 使用所有令牌。

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

示例 1：

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

示例 2：

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

示例 3：

输入：tokens = [100,200,300,400], P = 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], P < 104

解答

首先有必要重现描述一下题目的意思。能量P是我们获取分数score的钞票，最理想的情况下，我们有充足的能量P让让所有令牌朝上，这样可以获得数值等于数组长度的分数score。

最初的情况下，令牌不是正面朝上，也不是背面朝上，而是竖着的，如果我们把明码标价为price的令牌翻到正面朝上，则代价是相应数值的能量，获得的是加一的分数；否则，我们如果把这个令牌翻到背面朝上，则会获得该令牌上面标价的能量，代价是失去一分分数。这实际上是一个用能量P购买分数score的过程，限制条件是不能赊账，也就是能量不足price时不能把标价为price的令牌翻转到正面，score为零时不能把任何一个令牌翻转到反面。

贪心算法认为，我们需要把标价小的令牌翻转到正面以获得分数score，把标价大的令牌翻转到反面以获得能量P。

因此需要将数组进行排序。用现存的能量P从小到大把令牌翻正，同时获得分数，直到能量不够用了，就用现有的分数score把最大的令牌翻到反面以获取能量。这个过程一直持续到所有令牌都被翻过为止，因为令牌都是一次性的，使用中间变量res记录中途出现过的最大分数。

class Solution:
    def bagOfTokensScore(self, tokens, P):
        tokens.sort()
        res = scores = 0
        while tokens and (P >= tokens[0] or scores):

            while tokens and P >= tokens[0]:
                P -= tokens.pop(0)
                scores += 1

            res = max(res, scores)

            if tokens and scores:
                P += tokens.pop(-1)
                scores -= 1

        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析