#3898. 田忌赛马(C++四级)
田忌赛马(C++四级)
题目描述
你一定听过田忌赛马的故事吧? 如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。 请问田忌最多能赢多少银子?
关于输入
输入包含多组测试数据. 每组测试数据的第一行是一个整数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
解题分析
本题适合使用贪心算法,显然,我们要让田忌最小程度上亏损。先把田忌和齐王的马从小到大排序,然后从他们最强的马开始比起。如果田忌最强的马比齐王最强的马速度更快,则这局胜利。如果更弱呢?那肯定要输了,但是我们让田忌最弱的马去拼(这样损失最小)。如果一样强呢?那也肯定不能随便平局,我们就看看二者最弱的马,如果田忌最弱的马胜于齐王最弱的马,则先赢一把,然后找到一个田忌最弱的马速度也小于等于齐王最强的马,如果此时最弱的马要弱于齐王最强的马,则此局输。如果还是等于,则平局。我们采用双指针来模拟这个过程。
Limitation
1s, 1024KiB for each test case.