题目链接:https://www.luogu.org/problemnew/show/P3054

题解:对于x,y显然相遇的次数为vxtvyt=kcv_xt - v_yt = kc k为向下取整,要使得kk最大,显然要tt取到maxmax即结束的时刻。先按速度排序。那么要计算x=1n(vxtvyt)/c\sum\limits_{x=1}^{n}(v_xt - v_yt)/c 。就涉及到小数的相减并向下取整。对于任意两个小数a,ba,b 显然$\lfloor a - b\rfloor \neq \lfloor a\rfloor - \lfloor b\rfloor $ 只有当a的小数位大于b的小数位时他们才相等,否则要让ab+1\lfloor a\rfloor - \lfloor b\rfloor + 1.

所以我们只需要先对整数进行考虑,然后再把ans扣掉小数的逆序对。对于小数部分离散化+树状数组维护即可 具体操作可参考代码
    #include <bits/stdc++.h>
    #define pa pair<ll, ll>
    #define mp make_pair
    #define lowbit(x) ((x)&(-x))
    #define mem(i, a) memset(i, a, sizeof(i))
    using namespace std;
    typedef long long ll;
    const ll INF = 0x3f3f3f3f;
    const ll MAXN = 1e6 + 5;
    ll a[MAXN],c[MAXN];
    ll n,l,k;
    struct node {
        ll x,id;
        double d;
    }e[MAXN];
    bool cmp1(node a, node b) {
        return a.d < b.d;
    }
    bool cmp2(node a, node b) {
        return a.id < b.id;
    }
    void update(ll x) {
        for(ll i = x; i <= a[n]; i += lowbit(i))
            c[i] += 1;
    }
    ll query(ll x) {
        ll sum = 0;
        for(ll i = x; i ; i -= lowbit(i))
            sum += c[i];
        return sum;
    }
    int main() {
        cin >> n >> l >> k;
        for(ll i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        ll ans = 0, sum = 0;
     
        for(ll i = 1; i <= n; i++) {
            double t = (a[i] * ((double) (l * k) / (a[n]))) / (double)k;
            e[i].x = (ll) t;
            e[i].id = i;
            ans += (i - 1) * e[i].x - sum;
            sum += e[i].x;
            e[i].d = t - e[i].x;
        }
        sort(e + 1, e + n + 1, cmp1);
        ll cnt = 1;
        double now = e[1].d;
        e[1].d = 1; 
        for(ll i = 2; i <= n; i++) {
            if(e[i].d - now > 1e-6) cnt++, now = e[i].d;
            e[i].d = cnt;
        }
        sort(e + 1, e + n + 1, cmp2);
        for(ll i = n; i >= 1; i--) {
            ans -= query(e[i].d - 1);
            update(e[i].d);
        }
        cout << ans;
        return 0;
    }```