题目描述

你的初始能量为 P，初始分数为 0，只有一包令牌。

令牌的值为 token[i]，每个令牌最多只能使用一次，可能的两种使用方法如下：

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

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

样例

输入：tokens = [100], P = 50
输出：0

输入：tokens = [100,200], P = 150
输出：1

输入：tokens = [100,200,300,400], P = 200
输出：2

注意

• tokens.length <= 1000
• 0 <= tokens[i] < 10000
• 0 <= P < 10000

算法

(贪心) $O(n \log n)$

1. 考虑如下的贪心算法：首先将令牌按照能量值从小到大排序，然后尽可能从能量值最小的令牌开始获取分数。如果当前剩余能量值不足以购买当前的令牌，则卖掉分数，换取能量值最高令牌的能量后，获取当前令牌的分数。
2. 简单证明：我们肯定希望获取分数的令牌消耗的能量值尽可能小，而换取能量值时的令牌尽可能大；所以排序后，贪心地获取能量值较小令牌的分数；无法再获取时，卖掉分数换取尽可能多的能量，此时可以得到能量收益，而且不会损失分数（因为一定可以再获取到当前令牌的分数）。

时间复杂度

• 排序后仅需要线性扫描，故时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        int n = tokens.size();
        sort(tokens.begin(), tokens.end());

        int j = n - 1, power = P, points = 0;

        for (int i = 0; i <= j; i++){
            if (power >= tokens[i]) {
                power -= tokens[i];
                points++;
            }
            else {
                if (i == j || points == 0)
                    break;

                power = power + tokens[j] - tokens[i];
                j--;
            }
        }

        return points;
    }
};