田忌赛马 内存限制: 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% 的数据， n ≤ 200 , 000 n≤200,000 1

```cpp #include <iostream> // 引入排序函数 #include <algorithm> using namespace std; const int MAXN = 200005; int a[MAXN], b[MAXN]; // 比较函数，用于qsort排序 int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main() { int n; // 读取马匹数量 cin >> n; // 读取田忌的马匹速度 for (int i = 0; i < n; i++) { cin >> a[i]; } // 读取齐王的马匹速度 for (int i = 0; i < n; i++) { cin >> b[i]; } // 对田忌的马匹速度进行排序 qsort(a, n, sizeof(int), cmp); // 对齐王的马匹速度进行排序 qsort(b, n, sizeof(int), cmp); int left_a = 0, right_a = n - 1; int left_b = 0, right_b = n - 1; int score = 0; while (left_a <= right_a) { if (a[right_a] > b[right_b]) { // 田忌最快的马比齐王最快的马快，用田忌最快的马和齐王最快的马比赛 score++; right_a--; right_b--; } else if (a[right_a] < b[right_b]) { // 田忌最快的马比齐王最快的马慢，用田忌最慢的马和齐王最快的马比赛 score--; left_a++; right_b--; } else { if (a[left_a] > b[left_b]) { // 田忌最慢的马比齐王最慢的马快，用田忌最慢的马和齐王最慢的马比赛 score++; left_a++; left_b++; } else { if (a[left_a] < b[right_b]) { // 田忌最慢的马比齐王最快的马慢，用田忌最慢的马和齐王最快的马比赛 score--; } left_a++; right_b--; } } } // 输出田忌得分减齐王得分的最大值 cout << score << endl; return 0; } ``` 我在以往的开发过程中，碰到过以下几点需要格外小心处理的地方： 1. 排序的方向要保证正确，确保比较函数的返回值逻辑无误，否则排序结果可能不符合预期。 2. 在循环处理比较的过程中，要注意边界条件的判断，避免出现数组越界的问题。 3. 对于不同比较情况的处理逻辑要清晰，每一种情况的处理方式都要考虑全面，不然可能导致得分计算错误。 [2025-08-29 11:44:44 | AI写代码神器 | 673点数解答]