首页 > 代码库 > 2181 田忌赛马
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
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int n,a[2010],b[2010],ans,l1,l2,r1,r2; 5 int main() 6 { 7 cin>>n; 8 for(int i=1; i<=n; i++)cin>>a[i]; 9 for(int i=1; i<=n; i++)cin>>b[i];10 sort(a+1,a+n+1);11 sort(b+1,b+n+1);12 l1=1;l2=1;13 r1=n;r2=n;14 while(l1<=r1)15 {16 if(a[l1]>b[l2])17 {18 l1++,l2++,ans+=200;19 }20 else if(a[r1]>b[r2])21 {22 r1--,r2--,ans+=200;23 }24 else25 {26 if(a[l1]<b[r2])ans-=200;27 l1++,r2--;28 }29 }30 if(ans>0)cout<<ans;31 else cout<<0;32 }
2181 田忌赛马
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。