思路

好神仙啊。

这道题思路非常的巧妙。答案很容易可以知道，为

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*C*speed[i]}{maxSpeed*C} \rfloor \]

化简得：

\[ ans = \lfloor \sum_{i=1}^{n} \frac{L*speed[i]}{maxSpeed} \rfloor \]

如果我们统计括号内的实数集和的话，会出现一些只有在计算机上才会出现的恶心误差，所以我们可以考虑分开取整再求和。这里有一个小技巧，对于两个数而言：

\[ \lfloor a – b \rfloor = \begin{cases} \lfloor a \rfloor – \lfloor b \rfloor, a的小数部分 \leq b的小数部分 \\ \lfloor a \rfloor – \lfloor b \rfloor – 1, a的小数部分>b的小数部分 \end{cases} \]

在判断小数部分的时候，我们可以把小数部分之间的大小关系转化为余数之间的大小关系进行判断，答案默认减掉那个取整的1，然后用树状数组补全那些被误删的取整项。

代码

// FOJ2930.cpp
#include <bits/stdc++.h>
#define ll long long
#define lowbit(p) (p & -p)
using namespace std;
const ll MAX_N = 1e5 + 200;
ll n, l, c, spd[MAX_N], mxspd, f[MAX_N], tree[1000100];
void update(int num)
{
    num++;
    while (num <= mxspd)
        tree[num] += 1, num += lowbit(num);
}
ll sum(int num)
{
    num++;
    ll ans = 0;
    while (num)
        ans += tree[num], num -= lowbit(num);
    return ans;
}
int main()
{
    scanf("%lld%lld%lld", &n, &l, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &spd[i]);
    sort(spd + 1, spd + 1 + n), mxspd = spd[n];
    for (int i = 1; i <= n; i++)
        f[i] = (l * spd[i]) / mxspd;
    update((l * spd[1]) % mxspd);
    ll prefix = f[1], ans = 0;
    for (int i = 2; i <= n; i++)
    {
        prefix += f[i];
        ans += i * f[i] - prefix - i;
        update((l * spd[i]) % mxspd);
        ans += sum((l * spd[i]) % mxspd);
    }
    printf("%lld", ans);
    return 0;
}