Luogu P3054 [USACO12OPEN]跑圈Running Laps 题解

题意

农夫约翰让他的$ n (1 \leq n \leq 100,000) $头牛在长度为$ c $的跑道上进行跑$ l $圈的比赛,所有牛从同一起点,以不同的速度开始跑。直到当跑得最快的那一头牛跑完$ l $圈时,所有牛才同时停下。
约翰发现在跑圈过程中发生了几次“超越事件”。其定义是:在比赛结束前某时刻,奶牛$ x $已经超越了奶牛$ y $整整一圈,则称做一次“超越事件”。(注: 至少一圈 ,超越了$\frac{1}{2}$圈,或者超越了$\frac{1}{4}$圈等等都不算。且对于同一对奶牛$(x,y)$不会重复计算次数。)
约翰想知道比赛过程中发生了多少次“超越事件”。

思路

设第$i$头奶牛跑了$a_i$圈,显而易见,$a_i=v[i]*(l\div Max)$,其中$Max$为最大速度。
那么将奶牛按照跑的圈数从大到小排序,显而易见答案就是$\lfloor a_i – a_j \rfloor(i<j)$,于是你就可以写出一个$O(N^2)$的程序跑出很好的成绩了
那么想办法优化这个式子,通过乱搞发现$\lfloor a_i \rfloor – \lfloor a_j \rfloor(i<j)$和上面的式子很像啊,于是发现这两个式子最多只相差$1$。
那什么时候会相差$1$呢?举个栗子,当$a_i=2.5,a_j=1.9$时,这个式子就会多算$1$。但这个式子绝对不会少算。于是我们只要额外统计下多算的情况就好了。不难发现,当小数部分是逆序对时,此时就多算了。
所以把$a_i$分成整数部分$f[i].a$与余数部分$f[i].b$。(为什么不是小数部分呢?因为小数部分比较难以控制——精度问题严重,而除数都是一样的,都是$Max$,所以就用余数更简单啦)
接下来就是套树状数组求逆序对的板子了。
等等,你问我不多算的式子怎么求?直接统计个前缀和乱搞就好了呀…

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇