Luogu P3054 [USACO12OPEN]跑圈Running Laps 题解

(Updated: )
oi
,

题意

农夫约翰让他的$ 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#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();
}