Bag of Tokens (M)

题目

You have an initial power of P, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).

Your goal is to maximize your total score by potentially playing each token in one of two ways:

• If your current power is at least tokens[i], you may play the ith token face up, losing tokens[i] power and gaining 1 score.
• If your current score is at least 1, you may play the ith token face down, gaining tokens[i] power and losing 1 score.

Each token may be played at most once and in any order. You do not have to play all the tokens.

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

Example 1:

Input: tokens = [100], P = 50
Output: 0
Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.

Example 2:

Input: tokens = [100,200], P = 150
Output: 1
Explanation: Play the 0th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1st token since you cannot play it face up to add to your score.

Example 3:

Input: tokens = [100,200,300,400], P = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
1. Play the 0th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2nd token (300) face up, your power becomes 0 and score becomes 2. 

Constraints:

• 0 <= tokens.length <= 1000
• 0 <= tokens[i], P < 10^4

---

题意

给定不同价值的代币和整数power，有两种操作：

1. 当power值大于指定代币的价值时，可以消耗与价值相应的power将该代币朝上，并获得1点分数；
2. 当分数大于0时，可以消耗1点分数，将一个代币朝下，并获得相应价值的power。

每个代币仅可被操作一次。求可以得到的最大分数。

思路

贪心算法：先将代币按照价值升序排列，从左到右遍历，如果power足够，将当前代币朝上获得分数；如果power不够，将最右的代币朝下转换成power(只有当最右代币左边仍有代币可操作时)，因为最右的代币价值最大，保证一定能将之前的代币朝上。

---

代码实现

Java

class Solution {
    public int bagOfTokensScore(int[] tokens, int P) {
        Arrays.sort(tokens);
        int score = 0;
        int left = 0, right = tokens.length - 1;
        while (left <= right) {
            if (P >= tokens[left]) {
                score++;
                P -= tokens[left++];
            } else if (right - left > 1 && score > 0) {
                score--;
                P += tokens[right--];
            } else {
                break;
            }
        }
        return score;
    }
}