令牌放置 图解题解

令牌能正面买分、反面买体力，这题求的是什么

给一个令牌数组 tokens 和初始能量 power。每个令牌只能用一次：正面朝上，能量够付 tokens[i] 就花掉换 +1 分；反面朝下，手里有分就花 1 分换回 tokens[i] 那么多能量。求整场攒到的最高分。题面 tokens=[40,25,60,30,15,50]、power=35 时答案是 2。

每个令牌都要选正反、还要排顺序，硬枚举有多大

每个令牌要么正面买分、要么反面卖分、要么不用，先后顺序还能任意排。想穷举所有组合，方案数随令牌个数指数级膨胀，n 个令牌光排列就 n! 种，稍多几个就算不完。得找条规律把「买哪个、卖哪个」定死，不再逐个搜索。

买分挑最便宜、卖分挑最值钱，为什么这样贪最优

买分是在花能量，花得越省、后面能买的次数越多，所以每次都挑当前最便宜的令牌买，代价最小。卖分正相反：卖一次要付出宝贵的 1 分，当然要换回最多能量，也就是挑当前最值钱的。tokens 排序后最便宜的全在左边、最值钱的全在右边，正好左指针负责买、右指针负责卖，两头往中间夹。

还有个容易漏掉的量：分数会为换能量主动跌回去，但答案要的是整场里的最高点。所以另记一个 ans 追历史峰值，score 每涨到新高就刷新 ans，卖分让它回落时 ans 不动。

左右指针每一步怎么定买还是卖，什么时候收手

循环只在左指针不超过右指针时继续，每步看三种情况：能量够买最便宜的那张令牌，就正面朝上——能量减掉它、score 加 1、左指针右移，顺手用 ans 记峰值；买不动但手里还有分（score ＞ 0），就反面朝下卖最值钱的那张——能量加上它、score 减 1、右指针左移；既买不动又没分可卖，就直接跳出。两指针交错时同样停，返回 ans。

power=35 起手，两指针把这组 tokens 夹到底

先排序得 [15,25,30,40,50,60]，左右指针分踞两端，power=35、score 与 ans 都是 0。第一步 power=35 ≥ 15，买 15：power=20、score=1，ans 刷成 1。第二步 power=20 ＜ 25 买不动、还剩 1 分，卖 60：power=80、score=0。第三步 power=80 ≥ 25，买：power=55、score=1，ans 仍是 1。第四步 power=55 ≥ 30，买：power=25、score=2，ans 刷成 2。第五步 power=25 ＜ 40 买不动，卖 50：power=75、score=1。第六步 power=75 ≥ 40，买：power=35、score=2，ans 仍是 2。左指针越过右指针，循环停，返回 2。

排序扛住主要开销，空数组和开局卡死各怎么收场

整个流程时间 O(n log n)，瓶颈在排序；双指针只是一遍线性扫，额外空间 O(1)。两个边界要想清：tokens 为空时左指针在 0、右指针在 -1，循环条件一进就不成立，直接返回 0；开局 power 连最便宜的都付不起、score 又是 0，第一步撞上「既买不动又没分卖」跳出，答案是 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()
        ans = score = 0
        i, j = 0, len(tokens) - 1
        while i <= j:
            if power >= tokens[i]:
                power -= tokens[i]
                score, i = score + 1, i + 1
                ans = max(ans, score)
            elif score:
                power += tokens[j]
                score, j = score - 1, j - 1
            else:
                break
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int ans = 0, score = 0;
        for (int i = 0, j = tokens.size() - 1; i <= j;) {
            if (power >= tokens[i]) {
                power -= tokens[i++];
                ans = max(ans, ++score);
            } else if (score > 0) {
                power += tokens[j--];
                --score;
            } else {
                break;
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int ans = 0, score = 0;
        for (int i = 0, j = tokens.length - 1; i <= j;) {
            if (power >= tokens[i]) {
                power -= tokens[i++];
                ans = Math.max(ans, ++score);
            } else if (score > 0) {
                power += tokens[j--];
                --score;
            } else {
                break;
            }
        }
        return ans;
    }
}