UVa 1344 - Tian Ji -- the Horse Racing(贪心)

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

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博客 ,格式可能有所偏差。