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;
    }
};


回到顶部