浙江科技学院第十三届程序设计竞赛 1006-田忌赛马后传

不念不忘少年蓝@ 2022-07-28 01:25 91阅读 0赞

# 田忌赛马后传 #

##### Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) #####

##### Total Submission(s) : 1046 Accepted Submission(s) : 164 #####

#### Font: Times New Roman | Verdana | Georgia ####

#### Font Size: ← → ####

### Problem Description ###

田忌赛马相信大家都很熟悉了。。。齐王在吃过亏后洗心革面，努力钻研ACM，终于成为算法大神。他决定再次向田忌挑战，但同时他又很欣赏田忌，让他有赢的机会，于是改变了下规则：齐王和田忌各拥有n匹马，每匹马有一个速度值，快的马总是能战胜慢的马，当两匹马速度相同时为平局，现在，齐王规定每赢一场（即双方各挑出一只马决斗，用过的马不可再用）可以获得100金币，齐王要求田忌能过获得最多的金币。  
田忌听到后吓的不行，TMD我只会3只马的情况，多了我脑子不够用，于是求助也是算法大神的你，你能帮他解决吗？

### Input ###

有多组测试数据。第一行为齐王和田忌各自马的数量n（n<1000），接下来两行分别有n个整数，分别为田忌和齐王的马的速度v（v<10000)

### Output ###

对于每组数据，输出一行表示田忌能够获得的最多的金币数。

### Sample Input ###

3
    92 83 71
    95 87 74
    2
    20 20
    20 20

### Sample Output ###

100
    0

### Author ###

bytelin

#include<iostream>
    #include<algorithm>
    using namespace std;
    bool ran(int x,int y)
    {
         return x<y;
    }
    int main()
    {
        int k,i,j;
        while(cin>>k)
        {
                     if(k==0) break;
                     int tj[1001],king[1001];
                     for(i=0;i<k;i++) cin>>tj[i];
                     for(i=0;i<k;i++) cin>>king[i];
                     sort(tj,tj+k,ran);
                     sort(king,king+k,ran);
                     long int count=0;
                     int tj_min=0,tj_max=k-1;
                     int king_min=0,king_max=k-1;
                     while(tj_min<=tj_max)
                     {
                                          if(tj[tj_max]>king[king_max])
                                          {
                                                count++;
                                                tj_max--;king_max--;
                                          }
                                          else if(tj[tj_min]>king[king_min])
                                          {
                                                count++;
                                                tj_min++;king_min++;
                                          }
                                          else
                                          {
                                                if(tj[tj_min]<king[king_max])
                                                count--;
                                                tj_min++;king_max--;
                                          }   
                     }
                     cout<<count*100<<endl;
        }
       
        return 0;
    }