csp信奥赛C++高频考点专项训练之贪心算法 --【双指针贪心】：田忌赛马

csp信奥赛C++高频考点专项训练之贪心算法 --【双指针贪心】：田忌赛马

题目描述

我国历史上有个著名的故事： 那是在2300 23002300年以前。齐国的大将军田忌喜欢赛马。他经常和齐王赛马。他和齐王都有三匹马：常规马，上级马，超级马。一共赛三局，每局的胜者可以从负者这里取得200 200200银币。每匹马只能用一次。齐王的马好，同等级的马，齐王的总是比田忌的要好一点。于是每次和齐王赛马，田忌总会输600 600600银币。

田忌很沮丧，直到他遇到了著名的军师――孙膑。田忌采用了孙膑的计策之后，三场比赛下来，轻松而优雅地赢了齐王200 200200银币。这实在是个很简单的计策。由于齐王总是先出最好的马，再出次好的，所以田忌用常规马对齐王的超级马，用自己的超级马对齐王的上级马，用自己的上级马对齐王的常规马，以两胜一负的战绩赢得200 200200银币。实在很简单。

如果不止三匹马怎么办？这个问题很显然可以转化成一个二分图最佳匹配的问题。把田忌的马放左边，把齐王的马放右边。田忌的马 A 和齐王的 B 之间，如果田忌的马胜，则连一条权为200 200200的边；如果平局，则连一条权为0 00的边；如果输，则连一条权为− 200 -200−200的边……如果你不会求最佳匹配，用最小费用最大流也可以啊。 然而，赛马问题是一种特殊的二分图最佳匹配的问题，上面的算法过于先进了，简直是杀鸡用牛刀。现在，就请你设计一个简单的算法解决这个问题。

输入格式

第一行一个整数n nn，表示他们各有几匹马（两人拥有的马的数目相同）。第二行n nn个整数，每个整数都代表田忌的某匹马的速度值（$0 \le $ 速度值≤ 100 \le 100≤100）。第三行n nn个整数，描述齐王的马的速度值。两马相遇，根据速度值的大小就可以知道哪匹马会胜出。如果速度值相同，则和局，谁也不拿钱。

输出格式

仅一行，一个整数，表示田忌最大能得到多少银币。

输入输出样例 1

输入 1

3 92 83 71 95 87 74

输出 1

200

数据规模与约定

• 对于20 % 20\%20%的数据，1 ≤ N ≤ 65 1\le N\le 651≤N≤65；
• 对于40 % 40\%40%的数据，1 ≤ N ≤ 250 1\le N\le 2501≤N≤250；
• 对于100 % 100\%100%的数据，1 ≤ N ≤ 2000 1\le N\le20001≤N≤2000。

思路分析

这是一个经典的田忌赛马问题，目标是最大化田忌的净胜场次（每赢一场+200，平局0，输一场-200）。由于双方马的数量相同（n≤2000），我们可以使用贪心算法在O(n log n)时间内解决。

贪心策略（孙膑的计策推广）：

1. 将田忌的马速度数组t和齐王的马速度数组q分别按升序排序（下标从1开始）。
2. 使用四个指针：tl（田忌最慢马索引）、tr（田忌最快马索引）、ql（齐王最慢马索引）、qr（齐王最快马索引）。
3. 循环n次（每场比赛）：
   • 如果田忌最慢马 > 齐王最慢马：直接让两者比赛，田忌赢一场（+200），tl++，ql++。
   • 否则如果田忌最慢马 < 齐王最慢马：田忌最慢马必输，让它对齐王最快马（消耗对方强马），田忌输一场（-200），tl++，qr--。
   • 否则（两者最慢马速度相等）：比较田忌最快马与齐王最快马：
     • 如果田忌最快马 > 齐王最快马：让两者比赛，田忌赢一场（+200），tr--，qr--。
     • 否则（田忌最快马 ≤ 齐王最快马）：让田忌最慢马对齐王最快马（此时最慢相等，但对方最快可能≥田忌最快），如果田忌最慢马 < 齐王最快马则输（-200），相等则平（0），tl++，qr--。

该贪心策略能保证田忌获得最大收益。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,a[2005],b[2005];intmain(){scanf("%d",&n);for(inti=1;i<=n;++i)scanf("%d",&a[i]);// 田忌马for(inti=1;i<=n;++i)scanf("%d",&b[i]);// 齐王马sort(a+1,a+n+1);// 升序排序sort(b+1,b+n+1);inttl=1,tr=n,ql=1,qr=n,ans=0;while(tl<=tr){if(a[tl]>b[ql]){// 田忌最慢 > 齐王最慢 -> 赢ans+=200;++tl;++ql;}elseif(a[tl]<b[ql]){// 田忌最慢 < 齐王最慢 -> 输，用最慢对齐王最快ans-=200;++tl;--qr;}else{// 最慢相等if(a[tr]>b[qr]){// 田忌最快 > 齐王最快 -> 赢ans+=200;--tr;--qr;}else{// 田忌最快 <= 齐王最快 -> 用最慢对齐王最快if(a[tl]<b[qr])ans-=200;// 可能输或平++tl;--qr;}}}printf("%d\n",ans);return0;}

功能分析

• 输入：第一行整数n，第二行n个整数为田忌马的速度，第三行n个整数为齐王马的速度。
• 处理：排序后使用双指针贪心算法，模拟每一场比赛，累加田忌的收益。
• 输出：田忌能获得的最大银币数（整数，可能为负）。
• 复杂度：排序O(n log n)，贪心O(n)，总时间复杂度O(n log n)，空间O(n)，满足n≤2000的规模要求。
• 正确性：贪心策略基于“若己方最慢马能赢对方最慢马则直接赢；否则用己方最慢马消耗对方最快马；若最慢相等则根据最快马情况决策”，是经典最优解法，可证明得到最大收益。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}