首页 > 代码库 > codevs——2181 田忌赛马
codevs——2181 田忌赛马
2181 田忌赛马
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 钻石 Diamond
题目描述 Description
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？
输入描述 Input Description
第一行为一个正整数n ，表示双方马的数量。
第二行有N个整数表示田忌的马的速度。
第三行的N个整数为齐王的马的速度。
输出描述 Output Description
仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。
样例输入 Sample Input
3
92 83 71
95 87 74
样例输出 Sample Output
200
数据范围及提示 Data Size & Hint
n <= 1000
思路：
贪心！
代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 2001using namespace std;int n,a[N],b[N],ans;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); sort(a+1,a+1+n); sort(b+1,b+1+n); int i=1,j=1,i1=n,j1=n; while(i<=i1) { if(a[i]>b[j])//若最小（速度）的马大于对方的最小的马 {//那么我们就用他的马中的最小的马和国王的马进行作战 ans+=200;//这样一定是赢的情况 i++; j++; } else//若最小的马小等于对方的最小的马 if(a[i1]>b[j1])//比较二人最大的马 { ans+=200; j1--;//如果最大的马能打赢的话，就让这两匹马进行对战 i1--; } else//如果最大的马打不过对方最大的马 {//无论如何，这只有两种情况，一是最小的马比对方的马小，二是打成平手，这样都要进行i++,j1-- if(a[i]<b[j1])//就用最小的马顶他，消耗他最大的马 ans-=200;//这样是一定输的情况 i++; j1--; } } if(ans>0) printf("%d",ans); else printf("0"); return 0;}
codevs——2181 田忌赛马
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。