flag

软件学院大三党，每天一道算法题，第22天

题目介绍

你的初始能量为 P，初始分数为 0，只有一包令牌。

令牌的值为 token[i]，每个令牌最多只能使用一次，可能的两种使用方法如下：

如果你至少有 token[i] 点能量，可以将令牌置为正面朝上，失去 token[i] 点能量，并得到 1 分。 如果我们至少有 1 分，可以将令牌置为反面朝上，获得 token[i] 点能量，并失去 1 分。 在使用任意数量的令牌后，返回我们可以得到的最大分数。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/bag-of-tokens

思路

贪心算法： 如果让我们来玩令牌放置这个游戏，在让令牌正面朝上的时候，肯定要去找能量最小的令牌。同样的，在让令牌反面朝上的时候，肯定要去找能量最大的令牌。

只要还有能量，就一直让令牌正面朝上，直到没有能量的时候，让一个令牌反面朝上从而获得能量继续之前的操作。

一定要小心处理边界条件，不然很有可能会写出错误的答案。这里要牢牢记住，在有能量时候，只能让令牌正面朝上，直到能量不够用了才能让令牌反面朝上。

最终答案一定是在一次让令牌正常朝上操作之后产生的（永远不可能在让令牌反面朝上操作之后产生）

关键代码

public static int bagOfTokensScore(int[] tokens, int P){ Arrays.sort(tokens);//将令牌排序 int high=tokens.length-1;//从右往左的指针 int low=0;//从左往右的指针 int point=0; int ans=0; while (low<=high&&(P>=tokens[low]||point>0)){ while (low<=high&&P>=tokens[low]){//尽可能多得分，因此用while P-=tokens[low]; low++; point++; } ans= Math.max(ans,point);//最终答案一定是在一次让令牌正常朝上操作之后产生的 if(low<=high&&point>0){//只需要一个最大的就可以，不用while P+=tokens[high]; high--; point--; } } return ans; }