问题 24705 --【2014赛前模拟四】赛车

24705: 【2014赛前模拟四】赛车

时间限制: 5 Sec  内存限制: 256 MB
提交: 1  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

赛车 (running.pas/c/cpp)

 
【题目描述】

N辆赛车(1N编号)在长度为C的圆形赛道上跑L圈,N辆赛车从赛道的同一地点,同一时刻沿着同一方向出发,各辆赛车的速度有可能不一样(同一辆车在整个比赛中速度保持不变,不考虑启动等情况),当最快的赛车跑了L*C的距离到达终点时,比赛结束。

在赛车比赛的过程中,经常会出现超车现象,这里指的超车是两辆赛车xy,在某个时刻tt不超过比赛结束的时刻)出现x跑到y前面或y跑到x前面的情况。

现在主办方想知道在整个比赛过程中,出现了多少次超车现象?

【输入格式】

1行三个空格分隔的整数N, L, C (1 <= L,C <= 25,000) N<=100000

2N+1行,每行一个整数,其中第i+1行的整数Vi表示第i辆赛车的速度(1 <= Vi <= 1,000,000)。

【输出格式】

输出一个整数,表示总的超车次数。

【输入样例】

4 2 100

20

100

70

1

【输出样例】

4

【样例说明】

4辆车在长度为100的跑道上跑两圈,各辆车的速度分别为20100701

这场比赛持续了2个单位时间,因为最快的那辆车速度是100,跑两圈正好是总赛程的长度200。在这个过程中,有4次超车,分别2超越14 3超越14

【题目来源】

USACO 2012 US Open, Silver Divisio  Running Laps

来源

 

[提交][状态]