题意

LeetCode 948.令牌放置

解法

本题采用的是贪心算法。
具体贪法是：
令牌点数小的话，我们就利用能量来换取分数；令牌点数大的话，我们就利用分数来换取能量。
限制的话：
如果我们能量一直足够的话，就一直换取分数。
如果我们能量不够的话：

• 1. 分数为0，直接退出。
• 2. 分数不为0，且换取后当前剩余的令牌数大于2或者P+tokens[tail] >= 2*tokens[head]的话，就换取；否则，直接退出。(剩余令牌数为0，效益为负，剩余令牌数为1，效益为0)。

代码

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