令牌放置如何用贪心最大化分数？什么时候该用分数换能量？

简化版

令牌放置先排序。能量足够时，用最小令牌正面朝上换分数；能量不够但已有分数时，用最大令牌反面朝上换能量。全程记录最大分数。小令牌最适合买分，大令牌最适合在必要时回收能量。

详细版

令牌正面朝上会消耗能量、增加 1 分；反面朝上会消耗 1 分、增加能量。排序后用双指针：left 指向最小令牌，right 指向最大令牌。只要能买最小令牌，就买；买不了且有分数，就卖最大令牌补能量；否则结束。

这种贪心的原因是：买分时花最少能量最划算，卖分时换最多能量最划算。时间复杂度 O(n log n)，空间复杂度取决于排序实现。

完整版教学

一、题目里的两种操作分别在换什么

正面朝上：

power -= token
score += 1

反面朝上：

score -= 1
power += token

所以它不是单纯背包，而是能量和分数之间的交换。目标是过程中能达到的最大分数，不一定是最后分数。

二、为什么先排序

排序后，最小令牌在左边，最大令牌在右边。买分时希望花最少能量，因此优先买左边；卖分时希望换最多能量，因此优先卖右边。

操作	贪心对象	理由
正面买分	最小 token	同样得 1 分，花费越小越好
反面换能量	最大 token	同样掉 1 分，回血越多越好

记忆钩子：买分买最便宜的，回血卖最贵的。

这个排序让每一步选择都可以用双指针完成。

三、为什么能买就一直买

只要当前能量足够买最小令牌，就应该买。因为正面操作会增加分数，而分数既是目标，也是在之后换能量的资源。

例如 power=100，令牌 [100,200,300]：

买 100 => score=1, power=0
之后必要时可以卖 300 => power=300, score=0

如果一开始不买，就没有分数可以卖，也没有获得最大分数的机会。

四、为什么买不了时卖最大令牌

当能量不够买最小令牌时，要继续推进只能反面放一个令牌。反面放任意令牌都损失 1 分，所以应该选择能补最多能量的最大令牌。

power=50, score=1, tokens=[60,200]
卖 60 得 power=110
卖 200 得 power=250

卖 200 至少不比卖 60 差，因为它给后续购买留下更多能量空间。

五、代码模板

int bagOfTokensScore(int[] tokens, int power) {
    Arrays.sort(tokens);
    int left = 0, right = tokens.length - 1;
    int score = 0, ans = 0;
    while (left <= right) {
        if (power >= tokens[left]) {
            power -= tokens[left++];
            score++;
            ans = Math.max(ans, score);
        } else if (score > 0) {
            power += tokens[right--];
            score--;
        } else {
            break;
        }
    }
    return ans;
}

注意答案要记录历史最大分数，因为最后一次卖令牌可能让当前分数下降，但历史高点才是题目答案。

六、用例子推演

tokens=[100,200,300,400]，power=200：

买 100：power=100, score=1, ans=1
买不了 200，卖 400：power=500, score=0
买 200：power=300, score=1, ans=1
买 300：power=0, score=2, ans=2

最终最大分数是 2。中途卖分不是失败，而是为了换更多能量继续买。

七、常见误区与追问

误区：最后返回当前 score。 当前分数可能因为最后卖令牌下降，应该返回历史最大值。
误区：买分时买大令牌。 同样增加 1 分，买大令牌会浪费能量。
误区：卖分时卖小令牌。 同样损失 1 分，卖小令牌回血少。
追问：为什么不是动态规划？ 操作收益结构非常单调，排序后局部最优可以安全推进。
追问：没有分数还能卖吗？ 不能，反面操作需要消耗 1 分。
追问：复杂度是多少？ 排序 O(n log n)，双指针扫描 O(n)。

八、加强记忆

令牌放置就是“分数和能量交易”。买分时买最便宜的令牌，能买就买；买不起但手里有分，就卖最贵的令牌回血。答案记录历史最大分数，不是最后分数。这个题的贪心味道很纯，双指针只是排序后的执行工具。

简化版

详细版