【OpenJ_Bailian - 2287】Tian Ji -- The Horse Racing （贪心）-白红宇

【OpenJ_Bailian - 2287】Tian Ji -- The Horse Racing （贪心）

阅读量：5149 次

发布时间：2019-06-13

本文共 1246 字，大约阅读时间需要 4 分钟。

田忌赛马，还是English，要不是看题目，我都被原题整懵了，直接上Chinese吧

Descriptions:

田忌和齐王赛马，他们各有n匹马，依次派出一匹马比赛，赢了加200，输了减200，平局不加钱，问如何安排马的出场顺序，使得田忌赢的钱最多

Input

输入最多包含 50 组测试数据。对于每组测试数据，第一行包括一个正整数 n (n ≤ 1000)，表示每一方的马的数目。第二行中的 n 个整数，表示田忌的马的速度。第三行中的 n 个整数，表示齐王的马的速度。在最后一组测试数据之后，是只包含单个 0 的一行。

Output

对于每组测试数据，输出包含单个数的一行，表示田忌将从齐王那里赢得银两的最大值。

Sample Input

392 83 7195 87 74220 2020 20220 1922 180

Sample Output

题目链接：

题解都在代码上

AC代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #define mod 1000000007#define eps 1e-6#define ll long long#define INF 0x3f3f3f3f#define ME0(x) memset(x,0,sizeof(x))using namespace std;int n;int a[1005];int b[1005];int main(){ while(cin>>n,n) { ME0(a); ME0(b); int sum=0; for(int i=0; i
                   
                    >a[i];//田忌的马 for(int i=0; i
                    
                     > b[i];//齐王的马 sort(a,a+n);//排序 sort(b,b+n); int l1=0; int l2=0; int r1=n-1; int r2=n-1; while(l1<=r1) { //田忌最快的马比齐王最快的马快，则两者比 if(a[r1]>b[r2]) { sum+=200; --r1; --r2; } //田忌最快的马比齐王最快的马慢，则用田忌最慢的马和齐王最快的马比 if(a[r1]
                     
                      b[l2]) { sum+=200; ++l1; ++l2; }//否则，用田忌最慢的马和齐王最快的马比 else { if(a[l1]

转载于:https://www.cnblogs.com/sky-stars/p/11073032.html

你可能感兴趣的文章