Problem
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, losingtoken[i]
power, and gaining1
point. - If we have at least
1
point, we may play the token face down, gainingtoken[i]
power, and losing1
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:
tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000
Solution: Greedy + Two Pointers
Sort the tokens, gain points from the low end gain power from the high end.
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, Running time: 8 ms class Solution { public: int bagOfTokensScore(vector<int>& tokens, int P) { sort(begin(tokens), end(tokens)); int points = 0; int ans = 0; int i = 0; int j = tokens.size() - 1; while (i <= j) if (P >= tokens[i]) { P -= tokens[i++]; ans = max(ans, ++points); } else if (points > 0) { P += tokens[j--]; --points; } else { break; } return ans; } }; |