你的初始能量为 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
 

提示:

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

 

思路:

贪心策略  用最小的换分   最大的得能量

先对tokens进行排序,然后从前面较小能量的值换分数,然后用分数换后面较大的能量,
在从前面较小的能量值换分数

public int bagOfTokensScore(int[] tokens, int P) {	   
		int points=0;   //到某位置时的分数
		int left=0;
	        int right=tokens.length-1;
	        int res=0;	    
		Arrays.sort(tokens);  //数组排序
		//如果当前能量能够获得分数就获得  如果获得不了就从右找到最大的失去分数换能量
		while (left<=right) {
			if (P>=tokens[left]) {			
				P-=tokens[left++];  //能量减少
				points++;         //分数+1
				res=Math.max(res, points);
			}else if (points>0) { //至少有 1 分
				points--;
				P+=tokens[right--];			
			}else{ //手里既没有分数  能量又不足以翻转令牌
				break;
			}
		}
		return res;       
    }