算法思路解析

1‌. 排序处理‌：首先将双方的马匹按速度升序排序，这样可以方便地比较最快和最慢的马
2‌. 贪心策略‌：

• 当田忌最快的马比齐王最快的马快时，直接比赛，田忌赢200两
• 当田忌最快的马比齐王最快的马慢时，用田忌最慢的马消耗齐王最快的马，最小化损失
• 当双方最快的马速度相同时，比较最慢的马：
  • 如果田忌最慢的马更快，就用最慢的马比赛赢200两
  • 否则用田忌最慢的马消耗齐王最快的马

3. 双指针技巧‌：使用左右指针分别跟踪当前最快和最慢的马，逐步缩小比较范围

复杂度分析

• 时间复杂度‌：O(nlogn)，主要由排序操作决定
• 空间复杂度‌：O(n)，用于存储马匹速度

这个算法通过贪心策略在每一步做出局部最优选择，从而保证全局最优解。对于N≤2000的数据规模，该算法完全可以在1秒内完成计算。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;  // 输入马匹数量
    int tian[2005], king[2005];  // 定义田忌和齐王的马匹速度数组
    
    // 读取田忌和齐王的马匹速度
    for (int i = 0; i < n; i++) cin >> tian[i];
    for (int i = 0; i < n; i++) cin >> king[i];
    
    // 对双方马匹速度进行升序排序
    sort(tian, tian + n);
    sort(king, king + n);
    
    // 初始化指针：left指向最慢的马，right指向最快的马
    int tian_left = 0, tian_right = n - 1;
    int king_left = 0, king_right = n - 1;
    int money = 0;  // 田忌的总收益
    
    // 贪心策略核心循环
    while (tian_left <= tian_right) {
        // 情况1：田忌最快的马比齐王最快的马快
        if (tian[tian_right] > king[king_right]) {
            money += 200;  // 直接比赛，田忌赢200银币
            tian_right--;  // 双方都用掉最快的马
            king_right--;
        }
        // 情况2：田忌最快的马比齐王最快的马慢
        else if (tian[tian_right] < king[king_right]) {
            money -= 200;  // 田忌必输，用最慢的马消耗齐王最快的马
            tian_left++;   // 田忌用掉最慢的马
            king_right--;  // 齐王用掉最快的马
        }
        // 情况3：双方最快的马速度相同
        else {
            // 子情况3.1：田忌最慢的马比齐王最慢的马快
            if (tian[tian_left] > king[king_left]) {
                money += 200;  // 用最慢的马比赛，田忌赢200银币
                tian_left++;   // 双方都用掉最慢的马
                king_left++;
            }
            // 子情况3.2：田忌最慢的马不比齐王最慢的马快
            else {
                // 用田忌最慢的马消耗齐王最快的马
                if (tian[tian_left] < king[king_right]) {
                    money -= 200;  // 田忌输200银币
                }
                // 如果速度相同，不输不赢
                tian_left++;    // 田忌用掉最慢的马
                king_right--;   // 齐王用掉最快的马
            }
        }
    }
    cout << money << endl;  // 输出田忌的最大收益
    return 0;
}