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输入 13 92 83 71 95 87 74输出 1200数据规模与约定对于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)时间内解决。贪心策略孙膑的计策推广将田忌的马速度数组t和齐王的马速度数组q分别按升序排序下标从1开始。使用四个指针tl田忌最慢马索引、tr田忌最快马索引、ql齐王最慢马索引、qr齐王最快马索引。循环n次每场比赛如果田忌最慢马 齐王最慢马直接让两者比赛田忌赢一场200tlql。否则如果田忌最慢马 齐王最慢马田忌最慢马必输让它对齐王最快马消耗对方强马田忌输一场-200tlqr--。否则两者最慢马速度相等比较田忌最快马与齐王最快马如果田忌最快马 齐王最快马让两者比赛田忌赢一场200tr--qr--。否则田忌最快马 ≤ 齐王最快马让田忌最慢马对齐王最快马此时最慢相等但对方最快可能≥田忌最快如果田忌最慢马 齐王最快马则输-200相等则平0tlqr--。该贪心策略能保证田忌获得最大收益。代码实现#includebits/stdc.husingnamespacestd;intn,a[2005],b[2005];intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d,a[i]);// 田忌马for(inti1;in;i)scanf(%d,b[i]);// 齐王马sort(a1,an1);// 升序排序sort(b1,bn1);inttl1,trn,ql1,qrn,ans0;while(tltr){if(a[tl]b[ql]){// 田忌最慢 齐王最慢 - 赢ans200;tl;ql;}elseif(a[tl]b[ql]){// 田忌最慢 齐王最慢 - 输用最慢对齐王最快ans-200;tl;--qr;}else{// 最慢相等if(a[tr]b[qr]){// 田忌最快 齐王最快 - 赢ans200;--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的规模要求。正确性贪心策略基于“若己方最慢马能赢对方最慢马则直接赢否则用己方最慢马消耗对方最快马若最慢相等则根据最快马情况决策”是经典最优解法可证明得到最大收益。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}