田忌赛马
成绩 | 100 | 开启时间 | 2020年02月20日 星期四 20:25 |
折扣 | 0.8 | 折扣时间 | 2020年02月20日 星期四 20:25 |
允许迟交 | 是 | 关闭时间 | 2020年02月20日 星期四 20:25 |
输入文件 | horse.in | 输出文件 | horse.out |
【题目描述】田忌赛马(horse) POJ 2287
“田忌赛马”是历史上有名地揭示如何善用自己的长处去对付对手的短处,从而在竞技中获胜的事例。当时田忌和齐王赛马,他们各派出N匹马(N≤2 000)。每场比赛,输的一方将要给赢的一方200两黄金,如果是平局的话,双方都不必拿出钱。
每匹马的速度值是固定而且已知的,而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马,才能赢最多的钱?
【输入格式】
有多组数据,每一组数据第一行为一个正整数N(N≤1 000),表示双方马的数量。第二行有N个整数表示田忌的马的速度。第三行的N个整数为齐王的马的速度。全部数据结束以0表示。
【输出格式】
每组数据输出一行,为田忌赛马可能赢得的最多的钱,结果有可能为负。
【输入样例】
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
【输出样例】
200
0
0