本文涉及的基础知识点

贪心 决策包容性
C++算法：滑动窗口及双指针总结 反向双指针
C++前后缀分解

LeetCode948. 令牌放置

你的初始 能量 为 power，初始 分数 为 0，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
你的目标是通过有策略地使用这些令牌以 最大化 总 分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：
朝上：如果你当前 至少 有 tokens[i] 点 能量 ，可以使用令牌 i ，失去 tokens[i] 点 能量 ，并得到 1 分 。
朝下：如果你当前至少有 1 分 ，可以使用令牌 i ，获得 tokens[i] 点 能量 ，并失去 1 分 。
在使用 任意 数量的令牌后，返回我们可以得到的最大 分数 。
示例 1：
输入：tokens = [100], power = 50
输出：0
解释：因为你的初始分数为 0，无法使令牌朝下。你也不能使令牌朝上因为你的能量（50）比 tokens[0] 少（100）。
示例 2：
输入：tokens = [200,100], power = 150
输出：1
解释：使令牌 1 正面朝上，能量变为 50，分数变为 1 。
不必使用令牌 0，因为你无法使用它来提高分数。可得到的最大分数是 1。
示例 3：
输入：tokens = [100,200,300,400], power = 200
输出：2
解释：按下面顺序使用令牌可以得到 2 分：

1. 令牌 0 (100)正面朝上，能量变为 100 ，分数变为 1
2. 令牌 3 (400)正面朝下，能量变为 500 ，分数变为 0
3. 令牌 1 (200)正面朝上，能量变为 300 ，分数变为 1
4. 令牌 2 (300)正面朝上，能量变为 0 ，分数变为 2
   可得的最大分数是 2。
   提示：
   0 <= tokens.length <= 1000
   0 <= tokens[i], power < 10⁴

贪心

性质一：如果最优解是朝上了n1张。则一定是能量较小的n1张。否则换成最小的n1张，也是最优解。决策包容性。同理朝下的牌是能量最大的n2张牌。
性质二：这个初始能量+超下的牌的能量 必定 >= 这n张牌的能量。
推论一：n1 >= n2$⟺$ 分数必定为正。故只需要考虑能量为正。
推论二：nums排序后，朝上的牌是nums的前缀，朝下的牌是nums的后缀。两者不能重叠。
枚举前缀长度，计算后缀最小长度。随着i增加大，j减少。 反向双指针。
如果能量最小的牌大于power，无法放置任意牌。其它情况如果后缀的能量+power >=前缀能量：一张朝上一张朝下$\cdots$。分数变化为：+1 -1 +1 -1 $\cdots$ +1 +1 $\cdots$。根据性质一：一张超上、一张朝下后，能量增加。
时间复杂度：O(nlogn)

代码

核心代码

class Solution {
		public:
			int bagOfTokensScore(vector<int>& tokens, int power) {
				const int N = tokens.size();
				sort(tokens.begin(), tokens.end());
				if (tokens.front() > power) { return 0; }
				vector<int> preSum(tokens.size() + 1);
				partial_sum(tokens.begin(), tokens.end(), preSum.begin() + 1);
				int ans = 0;
				for (int i =1,j=0 ; i <= N; i++) {
					while (preSum.back() - preSum[N - j] + power < preSum[i]) {
						j++;
					}
					ans = max(ans, i - j);
				};
				return ans;
			}
		};

单元测试

vector<int> tokens;
		int power;
		TEST_METHOD(TestMethod11)
		{
			tokens = { 100 }, power = 50;
			auto res = Solution().bagOfTokensScore(tokens, power);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod12)
		{
			tokens = { 200,100 }, power = 150;
			auto res = Solution().bagOfTokensScore(tokens, power);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			tokens = { 100,200,300,400 }, power = 200;
			auto res = Solution().bagOfTokensScore(tokens, power);
			AssertEx(2, res);
		}