问题分析

我们有中期榜单 $(A_i, B_i)$ 和最终榜单 $(C_j, D_j)$，需要建立选手的对应关系，使得：

1. 中期分数 $B_i$ ≤ 对应最终分数 $D_j$
2. 国家一致（可通过修改实现）
3. 修改次数最少

关键观察：最小修改次数 = $N$ - 最大可保留的正确匹配数

核心思路

1. 问题转化

将问题转化为：找到最大的匹配，使得：

• 每个中期选手匹配一个最终选手
• $B_i \leq D_j$
• $A_i = C_j$（如果不相等，可以修改其中一个）

由于可以修改国家，条件3可以放宽：我们只关心能匹配多少对选手而不需要修改国家。

2. 贪心策略

由于分数序列都是严格递减的，我们可以使用贪心：

• 将两个榜单都按分数从高到低排序
• 使用双指针：一个指针遍历中期选手，一个指针遍历最终选手
• 对于每个中期选手，尝试匹配当前可用的、国家相同的最终选手

步骤2：贪心匹配

使用双指针扫描：

• i 指向当前中期选手
• j 指向当前最终选手
• 维护每个国家在最终榜单中可用的选手

复杂度分析

• 排序：$O(N \log N)$
• 双指针扫描：$O(N)$
• 可用选手维护：使用平衡树或排序列表，$O(N \log N)$
• 总复杂度：$O(N \log N)$，对于 $N \leq 2\times 10^5$ 可接受

正确性证明

贪心策略的正确性基于：

1. 分数单调性：由于分数严格递减，如果中期选手 $i$ 能匹配最终选手 $j$，那么中期选手 $i+1$ 也能匹配最终选手 $j$
2. 最佳匹配：优先匹配同国家选手，然后使用剩余可用选手，这样能最大化保留匹配
3. 无后效性：当前决策不会影响后续更优解

样例分析

样例1

中期: (3,500), (2,200), (1,100)
最终: (1,1000), (3,700), (3,400)

最优匹配：

• (3,500) ↔ (3,700) ✓（国家相同）
• (2,200) ↔ (3,400) ✗（国家不同，需要修改）
• (1,100) ↔ (1,1000) ✓（国家相同）

保留匹配数 = 2，修改次数 = 3 - 2 = 1

总结

这道题的关键在于：

1. 问题转化：最小修改次数 ⇔ 最大保留匹配数
2. 贪心匹配：利用分数单调性，按分数从高到低匹配
3. 国家处理：优先匹配同国家选手，再考虑其他可用选手
4. 复杂度优化：通过排序和双指针将复杂度降至 $O(N \log N)$

通过贪心策略，我们可以在 $O(N \log N)$ 时间内求出最优解。