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

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;

#define re  
#define int long long 
#define LD double

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x+'0');
            else write(x/10),pc(x%10+'0');
        }
        #undef gc
        #undef pc
}I;
#define File freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);

struct node{
    int a,b;
}f[100010];
inline int cmp(node x,node y){return x.a<y.a||(x.a==y.a&&x.b<y.b);}
class Array_Tree{//树状数组求逆序对
    private:
        int c[1000010];
    public:
        inline void add(int x,int y){for(;x<=1000000;x+=(x&(-x))) c[x]+=y;}
        inline int getsum(int x){re int s=0;for(;x>=1;x-=(x&(-x))) s+=c[x];return s;}
        inline int query(int l,int r){return getsum(r)-getsum(l);}
}T;
class Solve{
    private:
        int n,l,c,v[100010],ans,Max;
    public:
        inline bool init(){
            n=I.read();l=I.read();c=I.read();
            for(int i=1;i<=n;i++) v[i]=I.read(),Max=max(Max,v[i]);
            for(int i=1;i<=n;i++) f[i].a=v[i]*l/Max,f[i].b=v[i]*l%Max;//整数部分和小数部分
        }
        inline void solve(){
            sort(f+1,f+n+1,cmp);
            for(int sum=0,i=1;i<=n;i++){
                ans+=(f[i].a*(i-1)-sum)-T.query(f[i].b,1000000);//非多算部分-多算部分
                sum+=f[i].a;//更新前缀和
                if(f[i].b>0) T.add(f[i].b,1);//树状数组上传
            }
            I.write(ans);putchar('\n');
        }
}S;
signed main(){
//  File
    S.init();
    S.solve();
}
暂无评论

发送评论 编辑评论


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