← 返回题单
题单练习 贪心
← 上一题 下一题 →

A4312 | 田忌赛马

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

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

大约 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
C++ 编辑器
输入
输出