测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A4312. 田忌赛马

编程题 入门
知识点

题目描述

这是中国历史上一个著名的故事。

大约 2300 年前,田忌是齐国的大将,他经常与齐王等人赛马。齐王和田忌各有若干匹马,按速度快慢分为上等马、中等马、下等马三个等级——每个人的上等马都比自己的中等马快,中等马又比自己的下等马快;但就同一等级而言,齐王的马总是比田忌的略快一些。

军事家孙膑给田忌出了一个主意:用下等马对齐王的上等马(必输),用上等马对齐王的中等马(必胜),用中等马对齐王的下等马(必胜),最终三局两胜,反败为胜。这个故事告诉我们:在整体实力不占优的情况下,合理的出场顺序可以改变胜负。

现在我们把问题一般化:假设齐王和田忌各有 $n$ 匹马($n$ 不必是 $3$)。比赛共进行 $n$ 局,每局双方各派出一匹马进行对决,每匹马只能出场一次。对决的规则如下:

- 若田忌的马速度 **高于** 齐王的马,则田忌赢得该局,获得 $200$ 银元;
- 若田忌的马速度 **低于** 齐王的马,则田忌输掉该局,失去 $200$ 银元;
- 若双方速度相等,则为 **平局**,不赢不输。

齐王会按照固定的顺序派出自己的马,而田忌可以**任意安排**自己马的出场顺序。你的任务是:帮助田忌确定最优的出场方案,使得田忌最终获得的银元总数**最大**。

输入格式

输入包含至多 $50$ 个测试用例,每个测试用例的格式如下:

- 第一行:一个正整数 $n$,表示双方各有多少匹马。
- 第二行:$n$ 个整数,表示田忌每匹马的速度。
- 第三行:$n$ 个整数,表示齐王每匹马的速度。

输入以单独一行的一个 0 结束。

输出格式

对于每个测试用例,输出一行一个整数,表示田忌最多能获得的银元数。

输入输出样例

输入 #1
3
92 83 71
95 87 74
2
20 20
20 20
0
输出 #1
200
0

说明/提示

### 样例解释

第一个测试用例:田忌的马匹速度为 $\{92, 83, 71\}$,齐王的马匹速度为 $\{95, 87, 74\}$。

田忌可以用最慢的马 $71$ 对阵齐王最快的马 $95$,然后用最快的马 $92$ 对齐王次快的马 $87$,用中等马 $83$ 对齐王最慢的马 $74$。最后赢得 $200$ 银元。

第二个测试用例:双方两匹马速度完全相同,无论田忌如何安排出场顺序,每局都是平局,最终得 $0$ 银元。

### 数据范围

对于所有数据,满足:

- $1 \le n \le 1000$
- 每匹马的速度是一个正整数,且不超过 $10^9$
上一题 去做题 下一题