P3111. 数字序列比大小

解题思路

这道题很明显是一道贪心结合双指针的题目。由于平局情况的出现，本题难点在于我们如何地选择策略。

很容易想到我们可以采取类似田忌赛马的策略：为了使得 A 赢的尽可能多，每次出现 A 中元素较小的时候，我们总是选择这个较小的元素和 B 中尽可能大的数去分组。

首先需要将两个数组各自排序，方便考虑两个数组里的最值情况。

我们设置四个指针 ia_left、ia_right、ib_left、ib_right，分别指向 A、B 数组中尚未比较过的元素的最小值和最大值。其初始化为：

如下图所示：

在一个 while 循环中，比较 A 和 B 中尚未比较过元素的最小值，即 A[ia_left] 和 B[ib_left]。

情况一：A 中最小值大于 B 中最小值

若 A[ia_left] > B[ib_left]，由于选择 B 中的其他数字，可能会导致 A[ia_left] 无法获胜，故选择该组进行比较，A 获胜。

情况二：A 中最小值小于 B 中最小值

若 A[ia_left] < B[ib_left]，由于此时 A 中最小值小于 B 中的任意一个元素，我们不妨采取田忌赛马的策略，让 A[ia_left] 和 B[ib_right] 进行分组，B 获胜。

情况三：A 中最小值等于 B 中最小值

若 A[ia_left] == B[ib_left]，这是最复杂的情况。我们继续考虑 A 和 B 中尚未比较过元素的最大值，即 A[ia_right] 和 B[ib_right] 的情况。

子情况 3.1：A 中最大值大于 B 中最大值

若 A[ia_right] > B[ib_right]，此时若令 A[ia_left] 和 B[ib_right] 分组，由于 A[ia_right] 无论怎么配对都是必胜，但 A[ia_left] 原本可以平局的配对现在却输了，故不能采取这样的策略。因此让 A[ia_right] 和 B[ib_right] 分组，A 获胜。

子情况 3.2：A 中最大值小于等于 B 中最大值

若 A[ia_right] < B[ib_right]，由于此时 B[ib_right] 大于 A 中的任何一个元素，A 无论如何配对都必输，故仍然维持着田忌赛马的策略，令 A[ia_left] 和 B[ib_right] 分组，B 获胜。

若 A[ia_right] == B[ib_right]，此时固然可以令 A[ia_left] 和 B[ib_left]、A[ia_right] 和 B[ib_right] 两两分组，但剩余元素的比较可能会让 A 的失利场次增多。

以上图为例子，如果选择 A 的 1 和 B 的 1 分组，A 的 4 和 B 的 4 分组，那么剩下的 A 的 2 只能和 B 的 3 分组。A 的结果是平 2 负 1，这不是最优解。最优解仍为 A 的 1 和 B 的 4 分组，剩下就存在 A 的 2 和 B 的 1 分组，A 的 4 和 B 的 3 分组。A 的结果是胜 2 负 1，这样才是最优解。

故仍然应该选择 A[ia_left] 和 B[ib_right] 进行分组，此时丢失的分数，可能能够在 A[ia_right] 的其他配对中获取回来。

显然这种情况可以和上一种情况 A[ia_right] < B[ib_right] 合并在一起，即：

核心逻辑

本题核心逻辑其实就是田忌赛马，在 A[ia_left] 必定无法胜利的情况下（无论是必输还是可能平局），都尽量地让 A[ia_left] 和 B[ib_right] 配对。

复杂度分析

• 设每个序列的长度为 n。先对 A、B 两个数组分别排序，各为 O(n log n)，这是整体的瓶颈。
• 之后的 while 循环中，无论走进哪个分支，A 侧尚未比较的区间 [ia_left, ia_right] 每轮都恰好缩小 1：情况一和情况二让 ia_left 前进，情况三要么 ia_right 后退、要么 ia_left 前进。循环条件是 ia_left <= ia_right，因此循环恰好执行 n 轮，每轮只做常数次比较和指针移动，共 O(n)。
• 整体时间复杂度为 O(n log n)，由排序主导；比较阶段是线性的。
• 空间上排序原地进行，算法只额外使用四个指针（ia_left、ia_right、ib_left、ib_right）和 ans，除输入数组外辅助空间为 O(1)。