你要和田忌赛马。你们各自有 N 匹马，并且要进行 N 轮比赛，每轮比赛，你们都要各派出一匹马决出胜负。 你的马匹的速度分别为 𝑢 1 , 𝑢 2 , . . . 𝑢 𝑁 ，田忌的马匹的速度分别为 𝑣 1 , 𝑣 2 , 𝑣 𝑁   田忌会按顺序派出他的马匹，请问你要如何排兵布阵，才能赢得最多轮次的比赛？巧合的是，你和田忌的所有马匹的速度两两不同，因此不可能出现 平局 输入 第一行一个整数 。保证 1 <= 𝑁 <= 5 𝑒 4 接下来一行 个用空格隔开的整数，依次为 𝑢 1 , 𝑢 2 , . . . 𝑢 𝑁 ，表示你的马匹们的速度。保证 1 <= 𝑢 𝑖 <= 2 𝑁 接下来一行 个用空格隔开的整数，依次为 𝑣 1 , 𝑣 2 , . . . 𝑣 𝑁 ，表示田忌的马匹们的速度。保证 1 <= 𝑣 𝑖 <= 2 𝑁 输出 输出一行，表示你最多能获胜几轮。 样例输入 复制 3 1 3 5 2 4 6 样例输出 复制 2

这个问题是经典的“田忌赛马”问题。 田忌按顺序出马，你需要安排自己的马匹顺序来最大化获胜轮数。 解题思路 1. 将你和田忌的马的速度分别排序。 2. 使用贪心策略： - 用你最快的马和田忌最快的马比较。 - 如果你的最快马比田忌的最快马快，就赢这一轮，双方去掉最快马。 - 如果你的最快马比田忌的最快马慢，就用你最慢的马去输给田忌的最快马，减少损失。 - 如果你的最快马和田忌的最快马一样快（但题目说速度两两不同，所以不会平局，这里只是逻辑完整），比较最慢的马：如果你的最慢马比田忌的最慢马快，就用最慢马赢他最慢马；否则用最慢马输给田忌的最快马。 不过题目说田忌按顺序出马，而不是田忌也最优安排，所以这里田忌的出马顺序是固定的（\( v_1, v_2, \dots, v_N \)）。 你需要安排自己的马匹顺序去应对田忌的固定顺序，以赢得最多轮次。 具体算法 1. 把你的马排序（从小到大）。 2. 用双指针： - 田忌从 \( v_1 \) 到 \( v_N \) 依次出马。 - 对于田忌的每一匹马 \( v_i \)，在你的剩余马中选一匹刚好比它快的马（最小的满足 \( u_j > v_i \) 的马）去赢；如果没有比它快的马，就用你剩余最慢的马去输（因为反正赢不了，保留好马后面用）。 但这样直接做是 \( O(N^2) \)，需要优化到 \( O(N \log N) \)。 优化方法 用平衡树（如 multiset）存你的马。 对田忌的每一匹马 \( v_i \)，在你的 multiset 中找第一个比它大的马（upper_bound），如果有，就选这匹去赢，计数器加一，并删除这匹马；如果没有，就选最小的马去输（删除最小的马）。 这样每作是 \( O(\log N) \)，总复杂度 \( O(N \log N) \)。 代码实现 ```cpp #include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; int main() { int N; cin >> N; vector<int> u(N), v(N); for (int i = 0; i < N; i++) cin >> u[i]; for (int i = 0; i < N; i++) cin >> v[i]; multiset<int> myHorses(u.begin(), u.end()); int winCount = 0; for (int i = 0; i < N; i++) { auto it = myHorses.upper_bound(v[i]); if (it != myHorses.end()) { // 有比 v[i] 快的马，用它赢 winCount++; myHorses.erase(it); } else { // 没有比 v[i] 快的马，用最慢的马输 myHorses.erase(myHorses.begin()); } } cout << winCount << endl; return 0; } ``` 样例验证 输入： ``` 3 1 3 5 2 4 6 ``` 你的马：{1, 3, 5} 田忌出 2 → 选 3 赢（删除 3） 田忌出 4 → 选 5 赢（删除 5） 田忌出 6 → 没有比 6 快的，用 1 输（删除 1） 赢 2 轮，输出 2。 [2026-01-11 12:47:40 | AI问答 | 848点数解答]