A41779. 田忌赛马你一定听过田忌赛马的故事吧？如果3匹马变成1000匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子，平局的话不输不赢。请问田忌最多能赢多少银子?输入输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数，表示田忌的马的…
填空题
困难
知识点
题目描述
田忌赛马
你一定听过田忌赛马的故事吧？
如果3匹马变成1000匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子，平局的话不输不赢。
请问田忌最多能赢多少银子?
输入
输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数，表示田忌的马的速度，下一行也是n个整数，表示齐王的马的速度。 输入的最后以一个0表示结束。
输出
对每组数据，输出一个整数，表示田忌至多可以赢多少银子，如果田忌赢不了，就输出一个负数，表示田忌最少要输多少银子。
样例输入
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
样例输出
200
0
0
参考答案
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int a[maxn];//田忌的马的速度
int b[maxn];//齐王的马的速度
bool cmp(const int &a, const int &b){ return a>b;}
int main() {
int n;
while (cin >> n) {
if(n==0) return 0;
for (int i =0; i <n; i++)cin >> a[i];
for (int i =0; i <n; i++)cin >> b[i];
sort(a , a + n, cmp);
sort(b , b + n, cmp);
int la = 0, ra = n-1;
int lb = 0, rb = n-1;
int ans = 0;
while (la <= ra && lb <= rb) {
if (a[la]>b[lb]) {ans++;la++;lb++;}
else if (a[la]<b[lb]) {ans--;ra--;lb++;}
else {
if (a[la]==b[rb]) {ra--;rb--;}
else if (a[ra]>b[rb]) {ans++;la--;rb--;}
else {ans--;ra--;lb++;}
}
}
cout<<ans*200<<endl;
}
return 0;
}
上一题
下一题