算法思路解析

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

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

3‌. 双指针技巧‌：使用左右指针分别跟踪当前最快和最慢的马，逐步缩小比较范围。
这个算法的时间复杂度主要是排序的O(nlogn)和单次遍历的O(n)，总体为O(nlogn)，能够高效解决问题。

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

int main() {
    int n;
    // 循环处理多个测试用例，直到输入0为止
    while (cin>>n && n!=0) {
        int tian[1000], king[1000];
        // 读取田忌和国王的马匹速度
        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;  // 直接比赛，田忌赢
                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;  // 用最慢的马比赛，田忌赢
                    tian_left++;   // 双方都用掉最慢的马
                    king_left++;
                }
                // 子情况3.2：田忌最慢的马不比国王最慢的马快
                else {
                    // 用田忌最慢的马消耗国王最快的马
                    if (tian[tian_left] < king[king_right]) {
                        money -= 200;  // 田忌输
                    }
                    // 如果速度相同，不输不赢
                    tian_left++;    // 田忌用掉最慢的马
                    king_right--;   // 国王用掉最快的马
                }
            }
        }
        cout << money << endl;
    }
    return 0;
}