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

思路与贡献¶

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

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

因此答案是最长严格下降子序列长度。出题人的实现把序列划分成尽可能少的非下降链。维护按递增顺序排列的链尾 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\) 秒，余量接近两倍。性能结论仅针对所测环境和数据。