SSOJ1357田忌赛马
6142+
作者：crxis 发布：2017-06-27 分类：贪心
题目大意：田忌赛马，即田忌和齐王赛马，大家都有n匹马，比n场，每匹马比一次；先知道齐王马的出场顺序，请问田忌能赢多少场？
题目描述
中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？
输入
第一行为一个正整数n (n < = 10000) ，表示双方马的数量。 第二行有N个整数表示田忌的马的速度。 第三行的N个整数为齐王的马的速度。
输出
仅有一行，为田忌赛马可能赢得的最多的钱，结果有可能为负。
样例输入
3
92 83 71
95 87 74
样例输出
200
解题思路
从好的马开始比较，如果田忌最好的马能赢，那么他必赢一场，也可以顺便K掉齐王最好的马，这对后面最有利；如果田忌最好的马会输，那先不用他，留在后面可能会赢，此时齐王最好的马必赢一场，那就损失一匹最差的马，比损失其他马更为有利。如果两匹马打平手，不能直接判断，需要看最弱的马，如3 5和4 5、4 5和3 5，交叉比则和，否则有输赢。
不管是从好的马开始比较，还是从差的马开始比较，都是可以的，关键在于，遇到相等的时候怎么办？如果最好的马力量相当，那就看最差的马，如果田忌最差的马能赢，则可以直接赢，因为赢齐王“好一点”的马也是没有意义的，那“好一点”的马迟早会输给田忌其他更好的马；如果田忌会输，则最差的马必输，输给齐王最好的马吧；如果打平手，那就跟齐王最强的比，如果输了，后面自己最强的马还能赢回来的。（齐王最好的马被田忌最差的马消耗了，但田忌最好的马不一定被齐王最差的马消耗，这样和最差跟最差比、最强跟最强比要有利。）
程序实现
