题意
LeetCode 948.令牌放置
解法
本题采用的是贪心算法。
具体贪法是：
令牌点数小的话，我们就利用能量来换取分数；令牌点数大的话，我们就利用分数来换取能量。
限制的话：
如果我们能量一直足够的话，就一直换取分数。
如果我们能量不够的话：
- 分数为0，直接退出。
- 分数不为0，且换取后当前剩余的令牌数大于2或者
P+tokens[tail] >= 2*tokens[head]的话，就换取；否则，直接退出。(剩余令牌数为0，效益为负，剩余令牌数为1，效益为0)。
- 分数不为0，且换取后当前剩余的令牌数大于2或者
代码
public class _948 {
static class Solution {
public static int bagOfTokensScore(int[] tokens, int P) {
if(tokens == null || tokens.length <= 0 || P <= 0){
return 0;
}
int head = 0;
int tail = tokens.length - 1;
Arrays.sort(tokens);
int res = 0;
while (head <= tail){
if(P >= tokens[head]){
P -= tokens[head++];
++res;
}else if(res > 0 && (tail - head >= 2 || (P + tokens[tail]) >= 2*tokens[head])){
P += tokens[tail--];
--res;
}else {
break;
}
}
return res;
}
}
}
