题目大意

在一个环形跑道上,有n个熊,每只熊分别有不同的速度。求在第一只熊冲过终点线的时候,发生了多少次“扣圈”(即一只熊从后面超过另一只熊)。

算法讲解

opt 1 算出每一只熊的跑步路程,再O(n^2)统计答案,50分。
opt 2 考虑优化统计答案的步骤,假设每一只熊跑的圈数为n,设n=x+y,x\in Z,0\leq y<1,即把圈数分成整数和小数部分,先按整数部分统计答案,对于任意的整数部分x_i>x_j,答案个数加上x_i-x_j。然而这样会多统计一些答案,例如3.75.3,虽然整数部分统计答案时算进去了2圈,但是实际上答案只能统计1圈。所以对于所有的n_i>n_j,如果存在y_i<y_j,那么答案就多统计了一圈,需要减一。整数统计问题就转化成了一个逆序对的问题,可以在O(n\log_2n)的时间复杂度内完成了。

细节问题

题目中强调了第一只熊冲过终点线的时间可能不为整数,并且路程和速度数量级为10^8
问题随即而来:若圈长为l,要求跑x圈时,第i只熊的圈数为n_i=\frac {l\time x\time v_i}{v_{max}\time l}=\frac {x\time v_i}{v_{max}}一定要考虑浮点数计算精度,否则会直接导致答案错误。
解决方法有二:
因为计算精度要求(10^8)^3位有效数字,所以在计算过程中开long double即可。
或者考虑优化存储方式,由于输入数据全部是正整数,可以直接用long long存储,并计算出整数部分(先乘后除);对于只需要比较大小的小数部分,每一个数乘上一个正实数后,大小关系不变,所以每一个y_i乘上分母v_{max}后比较大小,就避免了浮点计算的精度问题。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,c,n,l,m;
ll s[100010],v[100010],a[100010],b[100010],ans;
void balance(const int &l,const int &r){
    if(l==r)return;
    int mid=l+r>>1;
    balance(l,mid);
    balance(mid+1,r);
    register int p=l,q=mid+1,t=l;
    while(t<=r)
        if(p>mid)
            ans-=(mid-p+1),
            b[t++]=a[q++];
        else if(q>r)
            b[t++]=a[p++];
        else if(a[p]<=a[q])
            b[t++]=a[p++];
        else
            ans-=(mid-p+1),
            b[t++]=a[q++];
    for(int i=l;i<=r;i++)a[i]=b[i];
}
int main(){
    freopen("running.in","r",stdin);
    freopen("running.out","w",stdout);
    scanf("%d%d",&t,&c);
    while(t--){
        scanf("%d%d%d",&n,&l,&m);ans=0;
        for(int i=0;i<n;i++)scanf("%lld",&v[i]);
        sort(v,v+n);
        for(int i=0;i<n;i++)
            s[i]=m*v[i]/v[n-1],a[i]=v[i]*m-s[i]*v[n-1];
        ll tt=0;
        for(int i=0;i<n;i++){
            if(s[i]>s[i-1])tt+=(s[i]-s[i-1])*i;
            ans+=tt;
        }
        balance(0,n-1);
        printf("%lld\n",ans);
    }
}

"Alone is what I have. Alone protects me." -Sherlock Holmes