问题 5377. -- 赛马-训练套题T18T3

5377: 赛马-训练套题T18T3

时间限制: 1 Sec  内存限制: 128 MB
献花: 25  解决: 14
[献花][花圈]

题目描述

第三题:赛马(horse.pas/in/out

【问题描述】

齐国的将军田忌经常同齐威王赛马。他们赛马的规矩是:当两匹马比赛时,速度值大的一方会获胜,胜的一方赢1两黄金,输的一方赔1两黄金。如果两马匹的速度值相同,则为平局,双方都不赚不赔。当然,同一匹马只能比赛一次。

现知道齐威王和田忌两人的所有马的速度值。并且齐威王总是按速度从大到小的顺序出马,希望你给出一种最优策略,并求出田忌最多能赢(或者最少赔)多少钱。

【输入文件】

第一行:一个整数N,表示双方各有N匹马

第二行:N个正整数,分别表示齐威王每匹马的速度值

第三行:N个正整数,分别表示田忌每匹马的速度值。

【输出文件】 只有一个整数,表示田忌最多赢(最少赔)多少两黄金。

【样例输入1

3

2 4 6

1 3 5

【样例输出1

1

【样例输入2

10

3 6 1 7 6 3 6 2 2 10

2 1 1 5 1 2 3 2 1 10

【样例输出2

-1

【数据范围】

N<=5000

0<=速度值<=500

输入

输出

提示

来源

[献花][花圈]