首页 > 代码库 > hdu1052(田忌赛马 贪心)
hdu1052(田忌赛马 贪心)
好坑的一道题，不过确实是贪心的一道好题，想了好久一直无法解决平局的情况。 参考了别人的思路，然后结合了自己的想法，总算是想出来了。
这题有些步骤是必须要执行的，有四个步骤
一、当期状态田忌的最慢的马比对手最慢的马快，那么就直接比赢了这一盘，因为对手最慢的马比田忌所有马都慢，田忌为了后面的情况最优就用最小的代价来赢得这一个必胜的局。 二、当前状态田忌最慢的马比对手最慢的马慢，说明田忌最慢的马比对手所有的马慢，对于这个必败的情况田忌自然会用这匹马去耗对手最快的马，所以这局用最慢的马去和对手最快的马比。
三、同理，当前状态田忌最快的马比对手最快的马快，则比这盘
四、同理，当前状态田忌最快的马比对手最快的马慢，则用田忌最慢的马来耗队友最快的马。 因为对手最快的马怎么都要赢，所以要尽量减少损失。
也就是只要出现了这四种情况的其中一种，则必按上述步骤执行。但是还有一种情况，那就上述四种情况突然出现了两种，那么到底先执行哪一种呢？ 仔细想下就可以发现，先执行那一种情况最后的结果是相同的。
最后还可能会出现一种死局，那就是两头都相等的时候，这时候你可以假设一下用田忌最慢的马去和对手最快的马比，会出现两种情况，一种是对手最快的马比田忌最慢的马快，但是田忌最快的马也比对手最慢的马快， 所以最坏情况田忌也可以使得除去最快最慢的马剩下来的马，与对手除去最快和最慢剩余下来的马，继续比较，这与两边都比成平局或者一边平局所到达情况相同。 第二种，是当前状态所有的马速度相同，这样任何一种策略得出的结果都是相同的。
按照这种思路，这题就可以解了。
hdu1052
#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <queue>#include <stdlib.h>using namespace std;#define N 1100int ga[N],gt[N];int main(){ int n; while(scanf("%d",&n)&&n) { for(int i=0;i<n;i++) scanf("%d",gt+i); for(int i=0;i<n;i++) scanf("%d",ga+i); sort(ga,ga+n); sort(gt,gt+n); int ans=0; int ab,ad,tb,td; ab=0,ad=n-1; tb=0,td=n-1; int sign=0; while(1) { if(sign==0) { if(gt[tb]>ga[ab]) { ans++; tb++; ab++; if(tb>td) break; } else if(gt[tb]<ga[ab]) { if(ga[ad]>gt[tb]) ans--; tb++; ad--; if(tb>td) break; } else { if(ga[ad]==gt[td]) { if(ga[ad]>gt[tb]) ans--; tb++;ad--; if(tb>td) break; } else { sign=1; //否者交换方式 } } } else { if(gt[td]>ga[ad]) { ans++; td--;ad--; if(tb>td) break; } else if(gt[td]<ga[ad]) { ans--; tb++; ad--; if(tb>td) break; } else { if(ga[ab]==gt[tb]) { if(ga[ad]>gt[tb]) ans--; tb++; ad--; if(tb>td) break; } else { sign=0; } } } } printf("%d\n",ans*200); } return 0;}
hdu1052(田忌赛马 贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。