题目详解

游戏规则回顾

• 玩家和庄家各有 $n$ 张牌，数值互不相同，范围 $[1, 2n]$。
• 每轮双方打出手牌顶部的牌，点数高者得 $1$ 分，赢的牌移除，输的牌放回自己手牌顶部。
• 玩家最多可以进行一次交换（交换自己手牌中的任意两张牌），目标是最大化最终得分。

---

关键观察

1. 游戏过程的本质

由于输的牌会回到顶部，这意味着：

• 如果玩家当前顶部的牌赢了，它被移除，下一轮用下一张牌去比。
• 如果玩家当前顶部的牌输了，它会被放回顶部，下一轮仍然用同一张牌去比，直到它赢为止。

换句话说：玩家手牌中，只有那些能够赢下当前庄家顶部牌的牌，才会被消耗掉并移出游戏；输的牌会一直卡在顶部，反复尝试。

2. 前缀最小值与后缀最大值

设玩家手牌为 $a_1, a_2, \dots, a_n$（从上到下）。

定义前缀最小值位置：

• 若 $a_{k_j}$ 是前 $k_j$ 张牌中的最小值，则 $k_1, k_2, \dots, k_s$ 是这些位置。
• 显然 $k_1 = 1$，且 $a_{k_1} > a_{k_2} > \dots > a_{k_s}$（严格递减）。

重要性质：
如果 $a_{k_j}$ 在某轮赢了庄家的牌 $b_t$，那么后面所有 $a_{k_{j+1}}, a_{k_{j+2}}, \dots$ 也都能赢 $b_t$，因为它们的数值更大（注意这里是 $a_{k_j}$ 是前缀最小值，所以 $a_{k_{j+1}}$ 比 $a_{k_j}$ 更小？ 需要小心）

实际上应该用后缀最大值来分析：
定义后缀最大值位置：
$suf\_max[i]$ 表示从 $i$ 到 $n$ 中最大值的下标。

但原标程中：

• $pref\_min[i]$ 存储前 $i$ 个元素中最小值的下标（值最小）。
• $suf\_max[i]$ 存储从 $i$ 到末尾中最大值的下标（值最大）。

为什么这样定义？因为一次交换的效果是：
将前缀最小值（弱牌）与后缀最大值（强牌）交换，可以提升前缀的战斗力。

---

3. 得分函数单调性

设 $f(k)$ 表示：如果玩家只考虑前 $k$ 轮（即前 $k$ 张手牌能稳定赢下前 $k$ 轮庄家牌），最大可能得分。

实际上，$f(k)$ 是单调不降的：

• 如果前 $k$ 张牌能赢 $k$ 轮，那么前 $k-1$ 张牌至少能赢 $k-1$ 轮（去掉最后一轮可能减少分数）。
• 更关键的是：如果能赢 $k$ 轮，那么一定能赢 $k-1$ 轮。

因此，我们可以二分答案：判断是否能得到至少 $mid$ 分。

---

4. 如何判断能否得至少 $mid$ 分

做法：

1. 找到前 $mid-1$ 个元素中的最小值位置 $p = pref\_min[mid-1]$。
2. 找到从 $mid$ 到末尾的最大值位置 $q = suf\_max[mid]$。
3. 交换 $a[p]$ 和 $a[q]$。
4. 用 $merge(a, b)$ 模拟游戏，计算实际得分。
5. 如果得分 $\ge mid$，则可行，否则不可行。
6. 交换回来恢复原数组。

为什么这样交换？

• 前 $mid-1$ 个元素中的最小值是最弱的牌，它很可能卡在顶部输掉很多轮。
• 从 $mid$ 到末尾的最大值是最强的牌，但位置靠后，前期用不上。
• 交换后，弱牌被放到后面，强牌被提到前面，能帮助赢得更多早期轮次。
• 为什么选 $pref\_min[mid-1]$ 和 $suf\_max[mid]$？
  因为我们要测试能否恰好赢 $mid$ 轮。如果前 $mid-1$ 个位置的最弱牌能换成后面最强的牌，那么前 $mid$ 张牌（新顺序）的战斗力会增强。

---

5. 模拟函数 merge

int merge(const vector<int> &a, const vector<int> &b) {
    int n = sz(a);
    int res = 0;
    for (int c = 0, i = 0, j = 0; c < n; ++c) {
        if (a[i] > b[j]) {
            ++res;
            ++i;
        } else if (a[i] < b[j]) {
            ++j;
        } else {
            assert(0);
        }
    }
    return res;
}

这个函数模拟了游戏过程：

• 用 $i$ 指向玩家当前顶部牌，$j$ 指向庄家当前顶部牌。
• 如果 $a[i] > b[j]$，玩家赢，$i$ 增加（该牌被移除）。
• 如果 $a[i] < b[j]$，玩家输，$j$ 增加（庄家牌被移除，玩家牌回到顶部，所以 $i$ 不变）。
• 注意：这里假设玩家输时，他的牌留在顶部，这正是规则。

最终 $res$ 就是玩家获胜的轮数。

---

6. 二分细节

初始：

• cur = merge(a, b) 是不交换时的得分。
• 下界 l = cur，上界 r = n。
• 二分查找最大可行的 $mid$。

为什么 $l$ 从 cur 开始？
因为不交换时已经得了 cur 分，答案至少是 cur。

---

7. 复杂度

• 每次二分判断 $O(n)$（一次 merge）。
• 二分次数 $O(\log n)$。
• 总复杂度 $O(n \log n)$，对 $n$ 总和 $2\times 10^5$ 可行。

---

8. 示例验证（第一个测试用例）

输入：

7
13 7 4 9 12 10 2
6 1 14 3 8 5 11

• 不交换时，merge 得 6 分（如题目说明）。
• 二分尝试 $mid=7$：
  找 $pref\_min[6]$：前 6 个最小值是 $4$（位置 3）。
  找 $suf\_max[7]$：从第 7 个到末尾最大值是 $2$（位置 7）。
  交换 $4$ 和 $2$，数组变 [13,7,2,9,12,10,4]。
  模拟发现无法得 7 分，所以 $l$ 保持 6。
• 输出 6。

---

总结

• 核心：利用一次交换把前缀最弱牌和后缀最强牌交换，提升早期胜率。
• 单调性允许二分答案。
• merge 函数正确模拟了“输牌回顶”的规则。