题目分析田忌和齐王分别由n匹马双方进行n轮比赛每轮各派一匹马出场每匹马只能使用一次 卖场数值大者拥有200银币求田忌最多的获益。求解思路田忌赛马中国人都知道的智慧两个人的马从大到小排田忌最大的齐王最大的直接200田忌最大的齐王最大的浪费齐王的好马用田忌最差的马对战齐王最好的。-200田忌最大的齐王最大的。这总不能打平把想想办法。最好的搁置看看最差的3.1 如果田忌最差的齐王最差的先200再说3.2 如果田忌最差的齐王最差的, 用田忌最差的去消耗齐王最好的如果田忌最差的齐王最好的则 -200。代码实现四指针分别指向田忌的最好和最差齐王最好和最差通过指针的变换指定马。#includebits/stdc.husingnamespacestd;inttian[2009],qi[2009];boolcmp(intx,inty){returnxy;}intmain(){intn,ans0;cinn;for(inti1;in;i)cintian[i];for(inti1;in;i)cinqi[i];sort(tian1,tiann1,cmp);sort(qi1,qin1,cmp);intt11,tnn,q11,qnn;while(t1tn){if(tian[t1]qi[q1]){ans200;t1;q1;}elseif(tian[t1]qi[q1]){tn--;//用田最差的q1;//齐王最好的ans-200;}else{if(tian[tn]qi[qn]){ans200;tn--;qn--;}else//让田最差的去耗齐王最好的{if(tian[tn]qi[q1])ans-200;tn--;q1;}}}coutans;return0;}也可也用双端队列#includeiostream#includealgorithm#includedequeusingnamespacestd;intmain(){intn;cinn;dequeinttian(n),king(n);for(inti0;in;i)cintian[i];for(inti0;in;i)cinking[i];// 从大到小排序sort(tian.begin(),tian.end(),greaterint());sort(king.begin(),king.end(),greaterint());intans0;while(!tian.empty()){if(tian.front()king.front()){// 田忌最快 齐王最快ans200;tian.pop_front();king.pop_front();}elseif(tian.front()king.front()){// 田忌最快 齐王最快ans-200;tian.pop_back();// 用最慢的送死king.pop_front();// 消耗对方最快的}else{// 田忌最快 齐王最快if(tian.back()king.back()){// 田忌最慢 齐王最慢ans200;tian.pop_back();king.pop_back();}else{// 田忌最慢 齐王最慢if(tian.back()king.front())ans-200;tian.pop_back();king.pop_front();}}}coutansendl;return0;}我的bug思路上的问题最开始当田忌最好的齐王最好的时先判断最差的此时田忌的最差的马 ≤ 齐王最差的马想法就直接用田忌最差的去消耗齐王最好的直接-200但是有没有可能田忌最差的也比齐王最好的强呢听起来匪夷所思但也不是不可能所以需要增加一个判断当田忌最差的比齐王最好的差时才会-200else{if(tian[tn]qi[qn]){ans200;tn--;qn--;}else//让田最差的去耗齐王最好的{//要判断一下田最差的小于齐最好的才会-200if(tian[tn]qi[q1])ans-200;tn--;q1;}}太严谨了其他思路贪心匹配中的尽量用刚好能赢的马去赢策略能赢则赢→ 不能赢就平→ 不行再输·阶段一能赢则赢从小到大枚举田忌的每一匹马ai在齐王尚未出战的马中寻找速度小于ai且最接近ai的马。如果找到了则进行比赛田忌胜出。如果没找到就先别急着让ai这匹马去送死先跳过继续处理ai1。这样能最大化地利用低速马换取胜利。·阶段二不能赢就平处理剩余的马对于田忌剩下的那些马它们谁也打不过最好的结果就是平局我们检查剩下的马中是否存在速度相等的若相等则计为平局。·阶段三不行再输剩余的无法平局的马只能算作负场。实现方法使用multiset将齐王的马全部存入std::multisetst。先找胜场遍历田忌排序后的马ai。二分寻找齐王最后一个没出战且小于ai的马。如果找到了记录田忌胜利并从集合中删除齐王这匹马。如果没找到将ai存入等待队列。再看平局在上一个步骤中田忌剩余的马尝试与齐王集合中剩余的马匹配平局最后平局剩下的则全部计为负场代码实现#includebits/stdc.husingnamespacestd;intmain(){intn,ans0;cinn;inta[n],b[n];for(inti0;in;i)cina[i];for(inti0;in;i)cinb[i];sort(a,an);multisetintst;//齐王的马都放入multiset中for(intx:b)st.insert(x);vectorintp;//存田忌的马中胜局没用的马intying0,ping0,shu0;for(inti0;in;i){//对于a[i]找最大的小于a[i]的数autoitst.lower_bound(a[i]);//大于等于a[i]if(it!st.begin())//找到了{--it;ans200;ying;st.erase(it);}else//没找到就将先先存下来{p.push_back(a[i]);}}//对于田忌的马中胜局没用的马看看能不能凑平局for(intx:p){autoitst.find(x);if(it!st.end())//找到了{ping;st.erase(it);}}shun-ying-ping;//coutpingendl;ans-shu*200;coutans;return0;}我的bug……疏忽多次尝试发现a数组固定长度或者长度为n都可以b如果是一个长度为 2009 的数组但只有前 n 个元素有输入值后面的都是随机值所以实际上st 中包含了n 个有效的齐王马的速度值(2009-n) 个随机的垃圾值会导致错误。也可以写成上面完成代码的形式或者用vector