Skip to content

948. Bag of Tokens

948. Bag of Tokens

题目: https://leetcode.com/problems/bag-of-tokens/

难度: Medium

题意：

  1. 玩个游戏，有n个游戏币，游戏币有权值，初始能量为P
  2. 每个游戏币只能被选择一次，每次只能在两种操作中选择其中一个操作
  3. 如果当前能量大于或等于该游戏币的权值，那么可以将能量减掉该游戏币的权值，分数+1
  4. 如果当前分数大于或等于1，那么可以将分数-1，将能量加上该游戏币的权值
  5. 问最多能得到多少分

思路：

  • 假设只有第一种操作，那么这个题就是个贪心题，排序，从小到大选择游戏币，直到能量用完
  • 第二种操作，相当于找一个权重小于或等于P的游戏币（命名为游戏币B），跟另一个游戏币（命名为游戏币A）同时去掉，然后能量加上游戏币A的能量
  • 游戏币A很容易想，肯定选择权重最大的那个，那游戏币B要挑哪个呢？
  • 答案是任意挑，因为对结果无影响。大家可以想一想，贪心算法相当于要求A[0]+A[1]+...A[k]<=P，k的最大，假设我们挑中了游戏币B来对冲游戏币A，那么下一轮的贪心问题就是A[0]+A[1]+...+A[k]-values(B)<=P+(values(A)-values(B))，可以看出，values(B)是被消去的
  • 所以解法就是，枚举所有的操作，每次操作把最小的置换最大的，剩下的就是求解贪心问题A[0]+A[1]+...A[k]<=P

解法：

class Solution {
public:
    int sum[10010];
    int getSum(int idx) {
        if (idx < 0) {
            return 0;
        } else {
            return sum[idx];
        }
    }
    int bagOfTokensScore(vector<int>& tokens, int P) {
        if (tokens.size() == 0) {
            return 0;
        }

        sort(tokens.begin(), tokens.end());
        sum[0] = tokens[0];
        for (int i = 1;i < tokens.size();i++) {
            sum[i] = sum[i - 1] + tokens[i];
        }

        int left = 0, right = tokens.size() - 1;

        int ret = 0;
        int res = 0;
        while (left <= right) {
            while (res <= right && getSum(res) - getSum(left - 1) <= P) {
                res++;
            }
            ret = ret > res - left ? ret : res - left;

            if (left == right) {
                break;
            }
            if (P >= tokens[left]) {
                P += tokens[right--] - tokens[left++];
            } else {
                break;
            }
        }
        return ret;
    }
};
回到顶部