首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; 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 &gt; b; } int main() {   while (cin &gt;&gt; n &amp;&amp; n) {     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; t[i];     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; k[i];     sort(t + 1, t + n + 1, cmp);     sort(k + 1, k + n + 1, cmp);     h1 = h2 = 1;     t1 = t2 = n;     while (h1 &lt;= t1) {       if (t[h1] &gt; k[h2])         ans += 200, h1++, h2++;       else {         if (t[h1] &lt; k[h2])           ans -= 200, t1--, h2++;         else {           if (t[t1] &gt; k[t2])             ans += 200, t1--, t2--;           else {             if (t[t1] &lt; k[h2])               ans -= 200;             t1--, h2++;           }         }       }     }     cout &lt;&lt; ans &lt;&lt; endl;     ans = 0;   } }</pre><pre class="brush:cpp;toolbar:false">// C++参考代码2 #include &lt;iostream&gt; #include &lt;algorithm&gt; using namespace std; int main() {     int n;     while (cin &gt;&gt; n &amp;&amp; n != 0) {         int tianji[1001], qiwang[1001];         for (int i = 0; i &lt; n; i++) {             cin &gt;&gt; tianji[i];         }         for (int i = 0; i &lt; n; i++) {             cin &gt;&gt; qiwang[i];         }         sort(tianji, tianji + n);         sort(qiwang, qiwang + n);         int tianjiIdx = 0, qiwangIdx = 0;         int profit = 0;         while (tianjiIdx &lt; n &amp;&amp; qiwangIdx &lt; n) {             if (tianji[tianjiIdx] &gt; qiwang[qiwangIdx]) {                 profit += 200;                 tianjiIdx++;                 qiwangIdx++;             } else if (tianji[tianjiIdx] &lt; qiwang[qiwangIdx]) {                 profit -= 200;                 tianjiIdx++;             } else {                 if (tianji[n - 1] &gt; qiwang[n - 1]) {                     profit += 200;                 }                 tianjiIdx++;                 qiwangIdx++;             }         }         cout &lt;&lt; profit &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">// C语言参考代码 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; 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", &amp;n) &amp;&amp; n) {         for (i = 1; i &lt;= n; i++) scanf("%d", &amp;t[i]);         for (i = 1; i &lt;= n; i++) scanf("%d", &amp;k[i]);         qsort(t + 1, n, sizeof(int), cmp);         qsort(k + 1, n, sizeof(int), cmp);         h1 = h2 = 1;         t1 = t2 = n;         while (h1 &lt;= t1) {             if (t[h1] &gt; k[h2])                 ans += 200, h1++, h2++;             else if (t[h1] &lt; k[h2])                 ans -= 200, t1--, h2++;             else if (t[t1] &gt; k[t2])                 ans += 200, t1--, t2--;             else if (t[t1] &lt; k[h2])                 ans -= 200, t1--, h2++;             else                 break;         }         printf("%d\n", ans);         ans = 0;     }     return 0; }</pre>
这道题暂未补解析。