# 红心女王的扑克士兵: 题解

## 思路与贡献

标准程序保留出题人的贪心链覆盖算法。Codex（GPT-6）整理 C++17 实现，补充严格不等号、相同属性及最优性的说明。程序见 [std.cpp](std.cpp)，树状数组补充解法见[中文题解](solution-alternative.zh.md)。

先按攻击力递增、同攻击力时按防御力递增排序。在这个顺序中，可行阵容恰好对应防御力的严格下降子序列：攻击力不同的一对必须反向比较防御力；攻击力相同的两人不能同时选择，而排序后的同攻击力段也不会提供严格下降的一对。

因此答案是最长严格下降子序列长度。出题人的实现把序列划分成尽可能少的非下降链。维护按递增顺序排列的链尾 `Chains` .读到防御力 $x$ 时，找最大的、不超过 $x$ 的链尾，把它替换成 $x$ ；若不存在这样的链尾，就在队首添加 $x$ .最终输出链数。`upper_bound` 返回第一个大于 $x$ 的位置，因此其前一个位置就是所需链尾。

## 正确性证明

每条链的防御力非下降，故严格下降子序列在一条链中至多选一个位置。任意时刻的链数都是答案的上界。

反转递增的链尾数组，得到严格递减的数组 $D$ .我们证明 $D_k$ 是已处理前缀中，长度为 $k$ 的严格下降子序列可达到的最大末尾值。空前缀时成立。处理 $x$ 时，算法替换第一个满足 $D_k\le x$ 的位置；若没有则追加一项。

若 $k>1$ ，前一项满足 $D_{k-1}>x$ ，对应子序列可以追加 $x$ ；$k=1$ 时单独选择 $x$ 即可。旧的 $D_k\le x$ ，所以这次更新得到更大的或相同的末尾。更短长度已有比 $x$ 大的末尾，无需更新；更长长度无法以 $x$ 结尾，否则去掉末项后会得到末尾大于 $x$ 、长度至少为 $k$ 的子序列，与旧 $D_k\le x$ 矛盾。追加时同理。因此不变量保持。

数组长度就是最长严格下降子序列的长度，也就是最优阵容大小。它与链数相同，所以输出正确。相同防御力只会替换链尾，不会错误增加答案；空输入输出零。

## 复杂度与实现

排序和每次二分共需 $O(n\log(n+1))$ 时间、$O(n)$ 空间；空输入只需常数工作。`deque` 支持随机访问，因此二分仍为对数时间，队首插入为常数时间。两属性均在有符号 32 位整数范围内。

参考环境测得标准程序最慢中位时间约为 $0.296$ 秒，预估时限为 $1$ 秒。树状数组方法具有相同渐进复杂度，但使用更多数组；其最慢中位时间约为 $0.489$ 秒，余量接近两倍。性能结论仅针对所测环境和数据。