| 题目名称 | 648. 田忌赛马 |
|---|---|
| 输入输出 | horsea.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-03-02加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：148， 提交：666， 通过率：22.22% | ||||
 Phosphorus15 |
100 | 0.000 s | 0.00 MiB | C++ |
 Extreme°/极致 ° |
100 | 0.000 s | 0.00 MiB | C++ |
 NVIDIA |
100 | 0.000 s | 0.00 MiB | C++ |
 @@@ |
100 | 0.000 s | 0.35 MiB | C++ |
 小e |
100 | 0.000 s | 0.35 MiB | C++ |
 サイタマ |
100 | 0.001 s | 0.35 MiB | C++ |
 new ioer |
100 | 0.004 s | 0.42 MiB | C++ |
 0 |
100 | 0.004 s | 1.05 MiB | C++ |
 金身人面兽 |
100 | 0.005 s | 0.35 MiB | C++ |
|
new ioer |
100 | 0.005 s | 0.42 MiB | C++ |
| 本题关联比赛 | |||
| 20120302 | |||
| 练习赛 | |||
| 关于 田忌赛马 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
你们是真的强。
 Apocana-Wisbtsml
2018-09-02 21:47
14楼
| ||||
|
| ||||
|
终于A过……
狂M……已经穷到数组开short了…… 然后g预处理还会特么超时 然后就一脸悲伤地现在才过 我给hzoi丢脸了…… | ||||
|
这么个题狂WA无数遍。。最后才发现自己答案初始化为0.。。
 _Itachi
2016-08-06 20:42
11楼
| ||||
|
表示是按照上面的贪心写的
 洛克索耶夫
2016-08-06 18:56
10楼
| ||||
|
贪心
1.当田忌最慢的马比齐王最慢的马快，赢一场先。因为始终要赢齐王最慢的马，不如用最没用的马来赢它。 2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场。因为田忌最慢的马始终要输的，不如用它来消耗齐王最有用的马。 3.当田忌最慢的和齐王最慢的马慢相等时，分4和5讨论。 4.当田忌最快的马比齐王最快的马快时，赢一场先。因为最快的马的用途就是来赢别人快的马，别人慢的马什么马都能赢。 5.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场，因为反正要输一场，不如拿最没用的马输。 6.当田忌最快的马和齐王最快的马相等时，这就要展开讨论了,贪心方法是，拿最慢的马来和齐王最快的马比. 显然是正确的！！！ 来自tyvj  SOBER GOOD BOY
2016-08-06 17:08
9楼
| ||||
|
打了一发Hungary的渣渣路过
| ||||
|
贪心水过
 YGOI_真神名曰驴蛋蛋
2016-08-06 15:06
7楼
| ||||
|
贪心贪错了。。
_Itachi
2016-08-06 14:53
6楼
| ||||
|
WA了2次，膜拜了@天一阁 笔记本上的题解才AC。
| ||||
NewBee
AntiLeaf
/k【问题描述】
齐国的将军田忌经常同齐威王赛马。他们赛马的规矩是：双方各下赌注，比赛共设三局，两胜以上为赢家。然而每次比赛田忌总是输家。
但用了孙膑之后，田忌每次都赢。
然而事后齐威王知道了孙膑助阵的事，于是大为不爽。他找来田忌要求重新赛马。为了防止田忌再次 cheat ，他将孙膑流放到了青岛二中实验楼的五楼去刷厕所。然后他重新制订了比赛的规则：对于每匹马有一个速度值。但两匹马比赛时，速度值大的一方会获胜，胜的一方赢 1 两黄金，输的一方赔一两黄金。如果两马匹的速度值相同，则为平局，双方都不赚不赔。当然，同一匹只能比赛一次。
聪明的孙膑即使是在刷厕所，仍然能知道齐威王和田忌两人的所有马的速度值。于是，他忍着双腿的疼痛，爬上了六楼，找到了正在读题的你，并把田忌的最优策略告诉了你，希望你去告诉田忌，但是你做的是一道很菜的题，一高兴就忘了田忌的最优策略。于是你只得自己求出田忌的最优策略，并求出田忌最多能赢多少钱。
【输入文件】
第一行：一个整数 N ，表示双方各有 N 匹马
第二行： N 个正整数，分别表示齐威王每匹马的速度值
第三行： N 个正整数，分别表示田忌每匹马的速度值。
【输出文件】
只有一个整数，表示田忌最多能赢多少两黄金。
【样例输入】
3
2 4 6
1 3 5
【样例输出】
1
数据范围
N<=5000
0<= 速度值 <=500