田忌赛马问题题解

一、题目分析

题目要求计算田忌通过合理安排马匹顺序，在与齐王的赛马中能获得的最大收益。关键条件：

1. 每匹马必须参赛且仅参赛一次；
2. 速度快的马必定战胜速度慢的马，平局不得分；
3. 每胜一局得200银元，每败一局扣200银元。

二、算法思路

1. 贪心策略：
   • 比较双方最快的马：
     • 若田忌最快的马 > 齐王最快的马，用田忌最快的马对阵齐王最快的马；
     • 若田忌最快的马 < 齐王最快的马，用田忌最慢的马对阵齐王最快的马；
     • 若双方最快的马速度相同，比较双方最慢的马：
       • 若田忌最慢的马 > 齐王最慢的马，用田忌最慢的马对阵齐王最慢的马；
       • 否则，用田忌最慢的马对阵齐王最快的马。

三、代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000+10;
int v1[maxn], v2[maxn];  // 田忌和齐王的马速

int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++)
            scanf("%d", &v1[i]);
        for(int i = 0; i < n; i++)
            scanf("%d", &v2[i]);
        
        // 排序：从小到大
        sort(v1, v1 + n);
        sort(v2, v2 + n);
        
        int ans = 0;  // 最终得分
        int cnt = n;  // 剩余比赛局数
        int max1 = n - 1, max2 = n - 1;  // 指向最快的马
        int min1 = 0, min2 = 0;          // 指向最慢的马
        
        while(cnt--) {
            if(v1[max1] > v2[max2]) {  // 田忌最快马 > 齐王最快马
                ans += 200;
                max1--; max2--;
            } else if(v1[max1] < v2[max2]) {  // 田忌最快马 < 齐王最快马
                ans -= 200;
                min1++; max2--;
            } else {  // 双方最快马速度相同
                if(v1[min1] > v2[min2]) {  // 田忌最慢马 > 齐王最慢马
                    ans += 200;
                    min1++; min2++;
                } else {  // 否则用田忌最慢马对阵齐王最快马
                    if(v1[min1] < v2[max2]) ans -= 200;  // 若田忌最慢马 < 齐王最快马，扣分
                    min1++; max2--;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

四、代码解释

1. 输入处理与排序：

   • 读取双方马匹速度并排序，以便快速获取最快和最慢的马。

2. 贪心策略实现：

   • 使用双指针max1、min1指向田忌的最快和最慢马；
   • 使用双指针max2、min2指向齐王的最快和最慢马；
   • 根据马匹速度比较结果，调整指针位置并更新得分。

3. 核心逻辑：

   • 优先用田忌最快的马击败齐王最快的马；
   • 若无法取胜，则用田忌最慢的马消耗齐王最快的马；
   • 当最快马速度相同时，比较最慢马，确保局部最优。

五、示例解析

输入样例1：

3  
92 83 71  
95 87 74  

1. 排序后：
   • 田忌：71, 83, 92
   • 齐王：74, 87, 95
2. 比赛过程：
   • 田忌最快马92 < 齐王最快马95，用田忌最慢马71对阵齐王最快马95，输一局；
   • 剩余马匹：田忌83, 92，齐王74, 87；
   • 田忌最快马92 > 齐王最快马87，用92对阵87，赢一局；
   • 剩余马匹：田忌83，齐王74；
   • 田忌最快马83 > 齐王最快马74，用83对阵74，赢一局；
3. 总得分：200银元。

六、复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作；
• 空间复杂度：O(n)，存储马匹速度。

七、关键技巧

1. 贪心策略：通过比较双方最快和最慢的马，做出最优选择；
2. 双指针优化：利用排序后的数组，通过双指针快速定位极值元素；
3. 平局处理：当最快马速度相同时，进一步比较最慢马，确保利益最大化。