A4312. 田忌赛马
编程题
入门
知识点
题目描述
这是中国历史上一个著名的故事。
大约 2300 年前,田忌是齐国的大将,他经常与齐王等人赛马。齐王和田忌各有若干匹马,按速度快慢分为上等马、中等马、下等马三个等级——每个人的上等马都比自己的中等马快,中等马又比自己的下等马快;但就同一等级而言,齐王的马总是比田忌的略快一些。
军事家孙膑给田忌出了一个主意:用下等马对齐王的上等马(必输),用上等马对齐王的中等马(必胜),用中等马对齐王的下等马(必胜),最终三局两胜,反败为胜。这个故事告诉我们:在整体实力不占优的情况下,合理的出场顺序可以改变胜负。
现在我们把问题一般化:假设齐王和田忌各有 $n$ 匹马($n$ 不必是 $3$)。比赛共进行 $n$ 局,每局双方各派出一匹马进行对决,每匹马只能出场一次。对决的规则如下:
- 若田忌的马速度 **高于** 齐王的马,则田忌赢得该局,获得 $200$ 银元;
- 若田忌的马速度 **低于** 齐王的马,则田忌输掉该局,失去 $200$ 银元;
- 若双方速度相等,则为 **平局**,不赢不输。
齐王会按照固定的顺序派出自己的马,而田忌可以**任意安排**自己马的出场顺序。你的任务是:帮助田忌确定最优的出场方案,使得田忌最终获得的银元总数**最大**。
大约 2300 年前,田忌是齐国的大将,他经常与齐王等人赛马。齐王和田忌各有若干匹马,按速度快慢分为上等马、中等马、下等马三个等级——每个人的上等马都比自己的中等马快,中等马又比自己的下等马快;但就同一等级而言,齐王的马总是比田忌的略快一些。
军事家孙膑给田忌出了一个主意:用下等马对齐王的上等马(必输),用上等马对齐王的中等马(必胜),用中等马对齐王的下等马(必胜),最终三局两胜,反败为胜。这个故事告诉我们:在整体实力不占优的情况下,合理的出场顺序可以改变胜负。
现在我们把问题一般化:假设齐王和田忌各有 $n$ 匹马($n$ 不必是 $3$)。比赛共进行 $n$ 局,每局双方各派出一匹马进行对决,每匹马只能出场一次。对决的规则如下:
- 若田忌的马速度 **高于** 齐王的马,则田忌赢得该局,获得 $200$ 银元;
- 若田忌的马速度 **低于** 齐王的马,则田忌输掉该局,失去 $200$ 银元;
- 若双方速度相等,则为 **平局**,不赢不输。
齐王会按照固定的顺序派出自己的马,而田忌可以**任意安排**自己马的出场顺序。你的任务是:帮助田忌确定最优的出场方案,使得田忌最终获得的银元总数**最大**。
输入格式
输入包含至多 $50$ 个测试用例,每个测试用例的格式如下:
- 第一行:一个正整数 $n$,表示双方各有多少匹马。
- 第二行:$n$ 个整数,表示田忌每匹马的速度。
- 第三行:$n$ 个整数,表示齐王每匹马的速度。
输入以单独一行的一个
- 第一行:一个正整数 $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$
第一个测试用例:田忌的马匹速度为 $\{92, 83, 71\}$,齐王的马匹速度为 $\{95, 87, 74\}$。
田忌可以用最慢的马 $71$ 对阵齐王最快的马 $95$,然后用最快的马 $92$ 对齐王次快的马 $87$,用中等马 $83$ 对齐王最慢的马 $74$。最后赢得 $200$ 银元。
第二个测试用例:双方两匹马速度完全相同,无论田忌如何安排出场顺序,每局都是平局,最终得 $0$ 银元。
### 数据范围
对于所有数据,满足:
- $1 \le n \le 1000$
- 每匹马的速度是一个正整数,且不超过 $10^9$