田忌赛马

╰+哭是因爲堅強的太久メ 2022-08-07 11:59 152阅读 0赞

## 1745: 田忌赛马 ##

Time Limit: 0 Sec   Memory Limit: 128 MB  
Submit: 47   Solved: 7  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

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

## Input ##

第一行为一个正整数n  (n  < =  1000)  ，表示双方马的数量。 第二行有N个整数表示田忌的马的速度。 第三行的N个整数为齐王的马的速度。

## Output ##

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

## Sample Input ##

3
    92 83 71
    95 87 74

## Sample Output ##

200

## HINT ##

## Source ##

[贪心算法][Link 1]

#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*200<<endl;
        }
    
        return 0;
    }

[Submit]: http://cst2.jlnu.edu.cn/acm/submitpage.php?id=1745
[Status]: http://cst2.jlnu.edu.cn/acm/problemstatus.php?id=1745
[Web Board]: http://cst2.jlnu.edu.cn/acm/bbs.php?pid=1745
[Link 1]: http://cst2.jlnu.edu.cn/acm/problemset.php?search=%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95