田忌赛马

Description

中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，
他们各派出N匹马（N≤2000），每场比赛，输的一方将要给赢的一方200两黄金，
如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，
而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢最多的钱？

Input

本题有多组测试数据，整个测试以数字零代表结束.
每组数据的第一行给出数字N，代表有多少匹马
第二行，给出田忌的每匹马的速度
第三行，则给出齐王的.

Output

输出田相最多可以赚到多少钱.

Sample Input

3
92 83 71
95 87 740

Sample Output

这道题是一道贪心的题目，只要你看过田忌赛马的故事，就很容易想到这道题大致的贪心路线，事实确实是这样。

现在列举一下

1、如果田忌的最慢的马要比齐王最慢的马快，先赢一场，这是肯定的。

2、如果田忌的最慢的马要比齐王最慢的马慢，就输给齐王最快的马，反正都是要输。

3、如果田忌的最快的马要比齐王最快的马慢，就拿田忌最慢的马去输。

4、如果田忌最快的马要比齐王最快的马快，就赢一场，这样的话价值最大，因为田忌最快的马要比齐王最快的都要快，就必定能赢一场，不如解决齐王实力最强的马。

看起来就只有这么多，然而是有例外的

那就是当最慢的马或是最快的马相等的时候，这个就不列举了，因为也是上面的处理方式，具体参考代码

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int h1,h2,t1,t2,n,i,ans=0;
 4 int t[100001],k[100001];
 5 int cmp(int a,int b)
 6 {
 7     return a>b;
 8 }
 9 int main()
10 {
11     while(cin>>n&&n)
12     {
13         for(i=1;i<=n;i++)cin>>t[i];
14         for(i=1;i<=n;i++)cin>>k[i];
15         sort(t+1,t+n+1,cmp);
16         sort(k+1,k+n+1,cmp);
17         h1=h2=1;
18         t1=t2=n;
19         while(h1<=t1)
20         {
21             if(t[h1]>k[h2])
22             ans+=200,h1++,h2++;
23             else
24             {
25                 if(t[h1]<k[h2])
26                 ans-=200,t1--,h2++;
27                 else
28                 {
29                     if(t[t1]>k[t2])
30                     ans+=200,t1--,t2--;
31                     else
32                     {
33                         if(t[t1]<k[h2])
34                         ans-=200;
35                         t1--,h2++;
36                     }
37                 }
38             }
39         }
40         cout<<ans<<endl;
41         ans=0;
42     }
43 }