UVa 1344 - Tian Ji -- The Horse Racing（贪心）

发表于 分类于 ， ， Disqus：

给出田忌和齐威王的马的属性，求田忌最多能赢多少钱。
类似于故事里的方法，排序后田忌最差的马若跑不过齐王最差的马，就和最好的马跑。最好的马优先与能比过的最好的马跑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1010;
int a[maxn],b[maxn];
int main(){
    int n;
    while(cin>>n,n){
        for(int i=0;i<n;++i) cin>>a[i];
        for(int i=0;i<n;++i) cin>>b[i];
        sort(a,a+n),sort(b,b+n);
        int sta1=0,sta2=0,ed1=n-1,ed2=n-1,win=0,lose=0;
        while(sta1<=ed1&&sta2<=ed2){
            if(a[sta1]<b[sta2]) ++sta1,--ed2,++lose;
            else if(a[sta1]>b[sta2]) ++sta1,++sta2,++win;
            else{
                if(a[ed1]>b[ed2]) --ed1,--ed2,++win;
                else if(a[ed1]<b[ed2]) ++sta1,--ed2,++lose;
                else{
                    if(a[sta1]<b[ed2]) ++lose;
                    ++sta1,--ed2;
                }
            }
        }
        cout<<(win-lose)*200<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章