题目描述

You have an initial power P, an initial score of 0 points, and a bag of tokens.

Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

• If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
• If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.

Return the largest number of points we can have after playing any number of tokens.

Example 1:

Input: tokens = [100], P = 50
Output: 0

Example 2:

Input: tokens = [100,200], P = 150
Output: 1

Example 3:

Input: tokens = [100,200,300,400], P = 200
Output: 2

Note:

1. tokens.length <= 1000
2. 0 <= tokens[i] < 10000
3. 0 <= P < 10000

题意：你的初始能量为 P，初始分数为 0，只有一包令牌。令牌的值为 token[i]，每个令牌最多只能使用一次，可能的两种使用方法如下：

如果你至少有token[i]点能量，可以将令牌置为正面朝上，失去token[i]点能量，并得到 1 分。
如果我们至少有 1 分，可以将令牌置为反面朝上，获得token[i]点能量，并失去 1 分。
在使用任意数量的令牌后，返回我们可以得到的最大分数。

算法1

(贪心/排序/双指针) $O(n^logn)$

题解：这道题的贪心的思路很清楚，我们在使用能量兑换积分的时候，尽可能兑换令牌值最小的那个令牌，在用积分兑换能量时，尽量兑换积分值较大的那个令牌。所以我们的整体思路如下：首先将令牌按照令牌值进行排序，同时使用双指针算法，i指针代表i位置之前的令牌都已经被用过了，j指针代表j位置后的令牌都已经用过了。我们首先尽可能将手上的能量P兑换成积分，并更新最大分数，如果此时分数为0，说明我们没有办法进行继续兑换了直接break，否则我们从后面选取令牌值最大的那个还没有被使用的令牌进行兑换并更新分数和能量值。

    int bagOfTokensScore(vector<int>& tokens, int P) {
        int n = tokens.size(),res = 0,grade = 0;
        sort(tokens.begin(),tokens.end());
        for(int i = 0,j = n - 1; i <= j ;)
        {
            while(i <= j && P >= tokens[i])
            {
                P -= tokens[i ++];
                grade ++;
            }
            res = max(res,grade);
            if(grade > 0 && i <= j)
            {
                P += tokens[j --];
                grade --;
            }else
                break;
        }
        return res;
    }