比赛场次 | 121 |
---|---|
比赛名称 | 20120302 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2012-03-02 19:00:00 |
结束时间 | 2012-03-02 22:00:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | 田忌赛马 |
---|---|
输入输出 | horsea.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
TBK | AAAWWWWAWW | 0.000 s | 0.00 MiB | 40 |
Cloud | AAAWWWWWWW | 0.000 s | 0.00 MiB | 30 |
Makazeu | AAWWWWWWWW | 0.000 s | 0.00 MiB | 20 |
11111111 | AAWWWWWWWW | 0.000 s | 0.00 MiB | 20 |
Czb。 | AAWWWWWWWW | 0.000 s | 0.00 MiB | 20 |
日光。 | AWWWTTTTTT | 0.000 s | 0.00 MiB | 10 |
苏轼 | AWWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
QhelDIV | WAWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
王者自由 | WAWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
Launcher | WWWWWWEWWW | 0.000 s | 0.00 MiB | 0 |
hello! | WWWWWWWWWW | 0.000 s | 0.00 MiB | 0 |
【问题描述】
齐国的将军田忌经常同齐威王赛马。他们赛马的规矩是:双方各下赌注,比赛共设三局,两胜以上为赢家。然而每次比赛田忌总是输家。
但用了孙膑之后,田忌每次都赢。
然而事后齐威王知道了孙膑助阵的事,于是大为不爽。他找来田忌要求重新赛马。为了防止田忌再次 cheat ,他将孙膑流放到了青岛二中实验楼的五楼去刷厕所。然后他重新制订了比赛的规则:对于每匹马有一个速度值。但两匹马比赛时,速度值大的一方会获胜,胜的一方赢 1 两黄金,输的一方赔一两黄金。如果两马匹的速度值相同,则为平局,双方都不赚不赔。当然,同一匹只能比赛一次。
聪明的孙膑即使是在刷厕所,仍然能知道齐威王和田忌两人的所有马的速度值。于是,他忍着双腿的疼痛,爬上了六楼,找到了正在读题的你,并把田忌的最优策略告诉了你,希望你去告诉田忌,但是你做的是一道很菜的题,一高兴就忘了田忌的最优策略。于是你只得自己求出田忌的最优策略,并求出田忌最多能赢多少钱。
【输入文件】
第一行:一个整数 N ,表示双方各有 N 匹马
第二行: N 个正整数,分别表示齐威王每匹马的速度值
第三行: N 个正整数,分别表示田忌每匹马的速度值。
【输出文件】
只有一个整数,表示田忌最多能赢多少两黄金。
【样例输入】
3
2 4 6
1 3 5
【样例输出】
1
数据范围
N<=5000
0<= 速度值 <=500