首页 > 代码库 > [HDU1052]Tian Ji -- The Horse Racing(田忌赛马)
[HDU1052]Tian Ji -- The Horse Racing(田忌赛马)
题目大意:田忌赛马问题,给出田忌和齐威王的马的数量$n$和每匹马的速度$v$,求田忌最多赢齐威王多少钱(赢一局得200,输一局扣200,平局不得不扣)。
思路:贪心。
1.若田忌最慢的马可以战胜齐王最慢的马,那么就让它战胜那匹慢马,胜利场次加1。(田忌最慢马 > 齐王最慢马)
2.若田忌最慢的马不能战胜齐王最慢的马,那么它更加不能战胜其他的马,那就让它输给齐王最快的马,失败场次加1。(田忌最慢马 < 齐王最快马)
3.若田忌最慢的马与齐王最慢的马速度相等。此时,打平是错误的。
因为自己的快马很有可能战胜此时对方的这匹慢马,所以就算自己输一场,快马也能帮忙赢回一场,而胜一场,输一场的收益和打平一场的收益是一样的相当于打平了一场。但区别在于自己输的时候可以用掉对方最快的马,给己方最快的马创造更大的胜利机会(因为它少了一个强劲的对手),也就是说己方最快的马很可能因为自己的牺牲再胜利一场,所以,输掉比打平的收益高。
但是如果己方最快的马原本就比对方最快的马快,则应该直接用己方最快的马和对方最快的马比赛,没必要再用己方最慢的马消耗掉对面最快的马。
根据思路写出代码。
C++ Code:
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int n; 5 int tj[1005],qww[1005],tslow,tfast,qslow,qfast; 6 int main(){ 7 while(~scanf("%d",&n)&&n){ 8 for(int i=0;i<n;i++)scanf("%d",&tj[i]); 9 for(int i=0;i<n;i++)scanf("%d",&qww[i]);10 sort(tj,tj+n);11 sort(qww,qww+n);12 int win=0,lose=0;13 tslow=qslow=0;14 tfast=qfast=n-1;15 while(tslow<=tfast){16 if(tj[tslow]>qww[qslow]){//情况117 win++;18 tslow++;19 qslow++;20 }else21 if(tj[tslow]<qww[qslow]){//情况222 lose++;23 tslow++;24 qfast--;25 }else //情况3 26 if(tj[tfast]>qww[qfast]){//特殊情况 27 win++;28 tfast--;29 qfast--;30 }else{31 if(tj[tslow]<qww[qfast])lose++;32 tslow++;33 qfast--;34 }35 }36 printf("%d\n",200*(win-lose));37 }38 return 0;39 }
[HDU1052]Tian Ji -- The Horse Racing(田忌赛马)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。