2181 田忌赛马

 时间限制: 1 s

 空间限制: 32000 KB

 题目等级 : 钻石 Diamond

 

 

 

题目描述 

Description

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

输入描述 

Input Description

第一行为一个正整数n ，表示双方马的数量。

第二行有N个整数表示田忌的马的速度。

第三行的N个整数为齐王的马的速度。

输出描述 

Output Description

仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。

样例输入 

Sample Input

3

92 83 71

95 87 74

样例输出 

Sample Output

200

数据范围及提示 

Data Size & Hint

n <= 1000

 

 

思路：

贪心！

代码：

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define N 2001using namespace std;int n,a[N],b[N],ans;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)     scanf("%d",&a[i]);    for(int i=1;i<=n;i++)     scanf("%d",&b[i]);    sort(a+1,a+1+n);    sort(b+1,b+1+n);    int i=1,j=1,i1=n,j1=n;    while(i<=i1)     {         if(a[i]>b[j])//若最小（速度）的马大于对方的最小的马          {
        //那么我们就用他的马中的最小的马和国王的马进行作战              ans+=200;//这样一定是赢的情况              i++;             j++;         }        else//若最小的马小等于对方的最小的马         if(a[i1]>b[j1])//比较二人最大的马         {            ans+=200;            j1--;//如果最大的马能打赢的话，就让这两匹马进行对战             i1--;        }        else//如果最大的马打不过对方最大的马         {
        //无论如何，这只有两种情况，一是最小的马比对方的马小，二是打成平手，这样都要进行i++,j1--             if(a[i]
               
                0) printf("%d",ans); else printf("0"); return 0;}