当前位置:首页 > 贪心 > 正文
SSOJ1357田忌赛马
5084+

题目大意:田忌赛马,即田忌和齐王赛马,大家都有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,交叉比则和,否则有输赢。

不管是从好的马开始比较,还是从差的马开始比较,都是可以的,关键在于,遇到相等的时候怎么办?如果最好的马力量相当,那就看最差的马,如果田忌最差的马能赢,则可以直接赢,因为赢齐王“好一点”的马也是没有意义的,那“好一点”的马迟早会输给田忌其他更好的马;如果田忌会输,则最差的马必输,输给齐王最好的马吧;如果打平手,那就跟齐王最强的比,如果输了,后面自己最强的马还能赢回来的。(齐王最好的马被田忌最差的马消耗了,但田忌最好的马不一定被齐王最差的马消耗,这样和最差跟最差比、最强跟最强比要有利。)

程序实现

About

坚决不Copy代码!

本文标签:,,

SSOJ1357田忌赛马:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!