题目出自杭电Tian Ji -- The Horse Racing
这个题感觉有很多坑。我这里用的是先从最坏马的角度开始。
1.首先如果田忌的最坏马比不过国王的最坏马，此时田忌的最坏马肯定要输，但是要让他输的最有价值————用它换掉国王最好的马！
2.如果田忌最坏的马能比得过国王最坏的马，此时就让田忌最坏的马赢 （能赢则赢）
3.然后最复杂的情况就是田忌的马和国王的马一样好，这个时候要从双方最厉害的马开始分类讨论。
3.1田忌最厉害的马比得过国王最厉害的马，此时让田忌最厉害的马赢，然后比双方次厉害的马，如果还是田忌赢则在比次次……
3.2田忌最厉害的马比不过国王最厉害的马，这个时候用田忌最坏的马换掉国王最厉害的马：
第一行是国王的马，第二行是田忌的马（！！！！不要看错）
只有这样是最优的。
**3.3接下来是最让人头疼的，如果田忌最厉害的马和国王最厉害的马一样厉害，那么我们要让田忌最坏的马去换掉国王最厉害的马（因为这样的收益是最高的————仔细体会这里)
然后3.3之所以会让人头疼，就是他还可能遇到一些奇葩数据(也就是我田忌最坏的马不一定比不过国王最好的马——比如极端情况: 所有马都一样好。这是我们就既不会输钱也不会赢钱)
——————————————————————————————————————————————————————————————————————————————————
害 明显感到我的表达还是存在问题(可能我还是理解的不是很透彻)
接下来上代码：
#include<iostream> #include<stdlib.h> using namespace std; #define N 10000 int a[N]; int a_begin,a_end; int b[N]; int b_begin,b_end; int com(const void *a,const void *b) { return *(int *)a - *(int *)b; } int main(){ int n; int money; while((cin>>n,n)){ for(int i = 0;i < n;i++){ scanf("%d",&a[i]); } for(int j = 0;j < n;j++){ scanf("%d",&b[j]); } a_begin = 0; a_end = n-1; b_begin = 0; b_end = n-1; qsort(a,n,sizeof(a[0]),com); qsort(b,n,sizeof(b[0]),com); money = 0; while(a_begin <= a_end){ if(a[a_begin] > b[b_begin]){ money++; a_begin++; b_begin++; } else if(a[a_begin] == b[b_begin]){ if(a[a_end] > b[b_end]){ money++; a_end--; b_end--; } else if(a[a_end] == b[b_end]){ if (a[a_begin] < b[b_end]) { money--; } a_begin++; b_end--; } else{ money--; a_begin++; b_end--; } } else{ money--; a_begin++; b_end--; } } printf("%d\n",money*200); } return 0; }
加油！！！小灰灰加油！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！