Tian Ji -- The Horse Racing 题解

· · 题解

题意

就是田忌赛马，赢一场比赛得+200银元，输了得-200银元，平局不加不减，求田忌最多能得到几个银元。

思路

这个题很显然是贪心，我们主要思想就是以小换大。 将齐王最快的马用我们最慢的马去换掉，这是最好的。

如果田忌最快的马比齐王最快的马快，就直接去比；

如果田忌最慢的马比齐王最慢的马快，也直接去比；

如果田忌最快的马比齐王最快的马慢，就用田忌最慢的马去比；

如果田忌最慢的马比齐王最慢的马慢，就和齐王最快的马去比；

我们可以用类似指针的方法做，la 是田忌最慢的马的下标，lb 是齐王最慢的马的下标，ra 是田忌最快的马的下标，rb ，是齐王最快的马的下标。

当然，我们必须在前面sort一下，从小到大排一遍序。

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e3+5;
int a[N],b[N];
signed main(){
    int n;
    while(cin>>n){
        if(n==0) return 0;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int j=1;j<=n;j++) cin>>b[j];
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        int la,lb,ra,rb;
        la=lb=1;//最慢的马
        ra=rb=n;//最快的马
        int res=0;
        for(int i=1;i<=n;i++){
            if(a[ra]>b[rb]){
                res+=200;
                ra--;
                rb--;
            }
            else if(a[ra]<b[rb]){
                res-=200;
                la++;
                rb--;
            }
            else if(a[la]>b[lb]){
                res+=200;
                la++;
                lb++;
            }
            else{
                if(a[la]<b[rb]){
                    res-=200;
                    la++;
                    rb--;
                }
            }
        }
        cout<<res<<endl;
    }
}

这道题居然只有一个测试点！！