Leetcode 948. Bag of Tokens

题目

948. Bag of Tokens

Difficulty: Middle
Total Accepted: 3,132
Total Submissions: 8,230

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:

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

解题报告

AC 截图

题目大意

初始状态下我们有 P 的能量，我们可以选择耗费 tokens[i] 的能量来将第 i + 1 个 token 换成一个点数，也可以耗费一个点数将第 i + 1 个 token 换成 tokens[i] 的能量。求最后最大的点数。

解题思路

本题中，我们可以采用一个贪心策略，即是先将 tokens 排序，每次需要获得能量时，选择最大能量的，否则选择最小能量的。如此一来，在 power 足够时，我们就尽量获取点数，否则尝试用一个点数去交换能量，直到所有 token 都被消耗，或者只剩一个 token，且无足够能量为止。

题解（最优解）

结果截图

C++ 代码

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        sort(tokens.begin(), tokens.end());
        if (tokens.size() == 0 || P < tokens[0]) return 0;
        int count = 0, sum = P, begin = 0, end = tokens.size() - 1;
        while (sum >= tokens[begin] && begin <= end) {
            sum -= tokens[begin++];
            ++count;
        }
        while (begin < end - 1) {
            sum += tokens[end--] - tokens[begin++];
            while (sum >= tokens[begin] && begin <= end) {
                sum -= tokens[begin++];
                ++count;
            }
        }
        
        return count;
    }
};