简答题
偏难
#7488
田忌赛马(2023.12) 你一定听过田忌赛马的故事吧? 如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢…
田忌赛马(2023.12)
你一定听过田忌赛马的故事吧?
如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。
请问田忌最多能赢多少银子?
时间限制:5000
内存限制:65536
输入
输入包含多组测试数据. 每组测试数据的第一行是一个整数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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// C++参考代码1
#include <bits/stdc++.h>
using namespace std;
int h1, h2, t1, t2, n, i, ans = 0;
int t[100001], k[100001];
int cmp(int a, int b) { return a > b; }
int main() {
while (cin >> n && n) {
for (i = 1; i <= n; i++)
cin >> t[i];
for (i = 1; i <= n; i++)
cin >> k[i];
sort(t + 1, t + n + 1, cmp);
sort(k + 1, k + n + 1, cmp);
h1 = h2 = 1;
t1 = t2 = n;
while (h1 <= t1) {
if (t[h1] > k[h2])
ans += 200, h1++, h2++;
else {
if (t[h1] < k[h2])
ans -= 200, t1--, h2++;
else {
if (t[t1] > k[t2])
ans += 200, t1--, t2--;
else {
if (t[t1] < k[h2])
ans -= 200;
t1--, h2++;
}
}
}
}
cout << ans << endl;
ans = 0;
}
}</pre><pre class="brush:cpp;toolbar:false">// C++参考代码2
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
while (cin >> n && n != 0) {
int tianji[1001], qiwang[1001];
for (int i = 0; i < n; i++) {
cin >> tianji[i];
}
for (int i = 0; i < n; i++) {
cin >> qiwang[i];
}
sort(tianji, tianji + n);
sort(qiwang, qiwang + n);
int tianjiIdx = 0, qiwangIdx = 0;
int profit = 0;
while (tianjiIdx < n && qiwangIdx < n) {
if (tianji[tianjiIdx] > qiwang[qiwangIdx]) {
profit += 200;
tianjiIdx++;
qiwangIdx++;
} else if (tianji[tianjiIdx] < qiwang[qiwangIdx]) {
profit -= 200;
tianjiIdx++;
} else {
if (tianji[n - 1] > qiwang[n - 1]) {
profit += 200;
}
tianjiIdx++;
qiwangIdx++;
}
}
cout << profit << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// C语言参考代码
#include <stdio.h>
#include <stdlib.h>
int h1, h2, t1, t2, n, i, ans = 0;
int t[100001], k[100001];
int cmp(const void* a, const void* b) {
return (*(int*)b - *(int*)a);
}
int main() {
while (scanf("%d", &n) && n) {
for (i = 1; i <= n; i++) scanf("%d", &t[i]);
for (i = 1; i <= n; i++) scanf("%d", &k[i]);
qsort(t + 1, n, sizeof(int), cmp);
qsort(k + 1, n, sizeof(int), cmp);
h1 = h2 = 1;
t1 = t2 = n;
while (h1 <= t1) {
if (t[h1] > k[h2])
ans += 200, h1++, h2++;
else if (t[h1] < k[h2])
ans -= 200, t1--, h2++;
else if (t[t1] > k[t2])
ans += 200, t1--, t2--;
else if (t[t1] < k[h2])
ans -= 200, t1--, h2++;
else
break;
}
printf("%d\n", ans);
ans = 0;
}
return 0;
}</pre>
这道题暂未补解析。