田忌赛马(贪心)------------看了一晚上，然后在CSDN和老师的帮助下我最终才完成____我好想一下子变成高手哇………………

题目出自杭电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;
}

 加油！！！小灰灰加油！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！