简答题 偏难
#7202

田忌赛马 你一定听过田忌赛马的故事吧? 如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到…

田忌赛马

你一定听过田忌赛马的故事吧?

如果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">#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>
这道题暂未补解析。