1059: 田忌赛马
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1320 Solved: 353
[Submit][Status][Web Board]
Description
田忌和齐王赛马,两人各出n匹马,赢一场比赛得200两银子,输了赔200银子,平局不赔不赚.已知两人每匹马的速度,问田忌最多能赢多少银子.
Input
多组测试数据,
每组数据的第一行是一个整数n。 (1<=n<=1000)
第二行包括n个整数既田忌每匹马的速度.
第三行包括n个整数既齐王每匹马的速度.
每匹马的速度不超过1000.
Output
对于每组数据输出一行有一个整数代表田忌最多能赢多少银子
Sample Input
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
Sample Output
200
0
0
贪心算法简单应用吧~思路见注释~
参考博客：https://blog.csdn.net/qq_41489727/article/details/80410707
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int a[maxn],b[maxn];
bool cmp(int a,int b){//降序 return a>b;
}
int main()
{int n;while(~scanf("%d",&n)){int i,j,lena,lenb;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)scanf("%d",&b[i]);sort(a,a+n,cmp);//降序排列 sort(b,b+n,cmp);i=0;j=0;int sum=0;lena=lenb=n-1;for(i,j;i<=lena;){if(a[lena]>b[lenb]){//如果田忌最慢的马比齐王最慢的马快，那么赢一场。sum++;lena--;lenb--;}else if(a[i]>b[j]){ //如果田忌最快的马比齐王最快的马快，也赢一场 sum++;i++;j++;}else{//.如果田忌最慢的马比齐王最慢的马慢或者最快的比最快的慢，那么田忌最慢的干齐王最快的，这样肯定会输，除了相等的情况。 if(a[lena]!=b[j])sum--;lena--;j++;}}cout<<sum*200<<endl;}return 0;
}