田忌赛马 内存限制: 256 Mb时间限制: 1000 ms 题目描述 田忌和齐王各有 n n 匹马，田忌的马速度分别为 a 1 , a 2 , … , a n a1,a2,…,a n ​ ，而齐王的马速度分别为 b 1 , b 2 , … , b n b1,b2,…,b n ​ 。 田忌与齐王比赛 n n 轮，双方每轮挑出一匹新马，若田忌的马更快，田忌加一分，若齐王的马更快，齐王加一分，若双方速度一样，分数不变。 齐王永远按照固定的顺序选择马匹参赛，田忌应该采取什么策略才能让自己的得分减齐王的得分变得最大？ 输入格式 第一行：单个整数 n n 第二行： n n 个整数 a 1 , a 2 , … , a n a1,a2,…,a n ​ 第三行： n n 个整数 b 1 , b 2 , … , b n b1,b2,…,b n ​ 输出格式 单个整数：表示田忌得分减齐王得分的最大值 数据范围 对于 30 % 30% 的数据， n ≤ 20 n≤20 对于 60 % 60% 的数据， n ≤ 2000 n≤2000 对于 100 % 100

```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; // 读取马匹数量 cin >> n; vector<int> tianji(n); vector<int> qiwang(n); // 读取田忌的马匹速度 for (int i = 0; i < n; ++i) { cin >> tianji[i]; } // 读取齐王的马匹速度 for (int i = 0; i < n; ++i) { cin >> qiwang[i]; } // 对田忌的马匹速度进行排序 sort(tianji.begin(), tianji.end()); int tianji_score = 0; int qiwang_score = 0; // 双指针，left指向田忌最慢的马，right指向田忌最快的马 int left = 0, right = n - 1; for (int i = 0; i < n; ++i) { if (tianji[right] > qiwang[i]) { // 若田忌最快的马比齐王当前马快，用最快的马比赛并获胜 tianji_score++; right--; } else if (tianji[left] > qiwang[i]) { // 若田忌最快的马不如齐王当前马，但最慢的马比齐王当前马快，用最慢的马比赛并获胜 tianji_score++; left++; } else if (tianji[left] < qiwang[i]) { // 若田忌最慢的马比齐王当前马慢，用最慢的马输掉比赛 qiwang_score++; left++; } // 若速度一样，分数不变，用最慢的马消耗齐王当前马 } // 计算田忌得分减齐王得分的最大值 int result = tianji_score - qiwang_score; cout << result << endl; return 0; } ``` 我在以往的开发过程中，碰到过以下几点需要格外小心处理的地方： 1. 排序操作是必要的，要确保对田忌的马匹速度进行排序，否则无法正确使用贪心策略。 2. 双指针的移动逻辑要清晰，不同情况下指针的移动要正确，避免出现指针越界等错误。 3. 对于速度相等的情况，要按照策略用最慢的马去消耗齐王的马，避免错误的判断。 [2025-08-29 11:43:43 | AI写代码神器 | 567点数解答]