首页 > 代码库 > codevs 2181 田忌赛马

codevs 2181 田忌赛马

2024-09-18 07:57:14   207人阅读

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

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int N=2003; 7 int n; 8  9 int king[N],me[N];10 int ans=0;11 12 int head=1,tail;13 14 bool cmp(int a,int b)15 {16     return a>b? 1 : 0;17 }18 int ans2=0;19 void work()20 {21     for(int i=1;i<=n+1;i++)22     {23         if(me[head]>king[n])head++,n--,ans+=200;24         else if(king[i]<me[tail])tail--,ans+=200;25         else 26         {27             if(king[i]>me[tail])head++,ans-=200;28         }29     }30 }31  32 int main()33 {34     scanf("%d",&n);tail=n;35     for(int i=1;i<=n;i++)scanf("%d",me+i);36     for(int i=1;i<=n;i++)scanf("%d",king+i);37     sort(king+1,king+n+1,cmp);38     sort(me+1,me+n+1);39     work();40     if(ans2>ans)ans=ans2;41     if(ans<0)cout<<0;42     else{43         printf("%d",ans);44     }45     return 0;46 }

 

codevs 2181 田忌赛马


联系
我们