你的初始能量为 P,初始分数为 0,只有一包令牌。
令牌的值为 token[i],每个令牌最多只能使用一次,可能的两种使用方法如下:
如果你至少有 token[i] 点能量,可以将令牌置为正面朝上,失去 token[i] 点能量,并得到 1 分。 如果我们至少有 1 分,可以将令牌置为反面朝上,获得 token[i] 点能量,并失去 1 分。 在使用任意数量的令牌后,返回我们可以得到的最大分数。
示例 1:
输入:tokens = [100], P = 50 输出:0 示例 2:
输入:tokens = [100,200], P = 150 输出:1 示例 3:
输入:tokens = [100,200,300,400], P = 200 输出:2
思路,尽可能的保证小能量的牌子得分,然后用大能量的牌子得到能量 所以先排序,然后用两个指针便利一遍数组即可。
注意:i和j可以指向同一个值,并且在获得大牌子能量时要保证score>0
class Solution { public: int bagOfTokensScore(vector<int>& tokens, int P) { sort(tokens.begin(),tokens.end()); int length = tokens.size(); if(length==0) return 0; int score = 0; int i=0 , j=length-1; while(i<=j)//第一次提交忘记等于,报错 { if(P>=tokens[i]){ score ++; P = P - tokens[i]; i++; } else if(score>0&&i<j-1){ score --; P = P + tokens[j]; j--; } else break; } return score; } };