948

948. Bag of Tokens (Medium)

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

Related Topics:
Greedy

Solution 1. Greedy + Two Pointers

Intuition: We would want to buy high value tokens using score and sell low value tokens to get scores.

So we should:

1. sort the tokens in asending order.
2. Try to use P to cover as much low value tokens as possible to get scores.
3. We buy the highest value token using one score, and add the value to P. If we can't buy any token, break.
4. Repeat step 2 and 3 until we've visited all tokens.
5. The final score we get is the answer.

// OJ: https://leetcode.com/problems/bag-of-tokens/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        sort(tokens.begin(), tokens.end());
        int i = 0, j = tokens.size() - 1, S = 0; // i points to the next low value token we can sell, j points to the next high value token we can buy, S is the score.
        while (i <= j) {
            while (i <= j && tokens[i] <= P) { // tokens[i] can be covered by `P`, sell it for score.
                P -= tokens[i++];
                S++;
            }
            if (i < j && S) { // if i == j, we can't sell any token after buying this token. So we only buy this tokens[j] if i < j and we have some score left.
                S--;
                P += tokens[j--];
            } else break;
        }
        return S;
    }
};