绕圈跑 题解

一、题目：

二、思路：

这是一道非常有代表性的题目，之前也同样碰到过类似这个题的难点。希望读者朋友能够耐心读完。

首先将v数组排序，最大的速度设为(v_m)。

设$$T=frac {l imes c }{v_m}$$表示最快的人跑完所花费的时间，即比赛的总时间。

对于每个（i,j），设(V_i>V_j)，则i同学追上j同学一圈所需时间为(frac {c}{V_i-V_j}).由于总时间为T，则能追上圈数为$$lfloor frac{T}{frac{c}{v_i-v_j}} floor$$.即$$lfloor frac {l imes v_i}{v_m}-frac{l imes v_j}{v_m} floor$$.
如果我们能把它拆成$$lfloor frac {l imes v_i}{v_m} floor-lfloor frac{l imes v_j}{v_m} floor$$就很棒了。我们就可以在瞬间计算出i的答案。

那么我们考虑这两个式子有什么区别。

设(X_i=lfloor dfrac{l imes v_i}{v_m} floor),(Y_i=(l imes v_i)mod v_m).
则(l imes v_i=X_i imes v_m +Y_i).

那么$$lfloor frac {l imes v_i}{v_m}-frac{l imes v_j}{v_m} floor =X_i-X_j+lfloor frac{Y_i-Y_j}{V_m} floor$$.

如果(Y_i-Y_j>=0),那么(lfloor frac{Y_i-Y_j}{V_m} floor=0)，上面两个式子就是相等的。
如果(Y_i-Y_j<0),那么(lfloor frac{Y_i-Y_j}{V_m} floor=-1)，这两个式子有1的差别。

于是我们对于每个i，用权值树状数组维护出有多少个j满足(Y_j>Y_i)，整道题就获得了解决。

小结一下，有很多问题都必须使用下取整，这时候用这种方法就可以高效的维护这些信息了。

三、代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long ll;
const int N = 1e5 + 3;

int n, c, t, Vmax, tr[N];
ll ans, sum, l;
struct cow {
	int speed, rank;
	cow(): speed(0), rank(0){}
	
	bool operator < (const cow &b) const {
		return speed < b.speed;
	}
} a[N];
struct BIT {
	int f[N];
	BIT(){ memset(f, 0, sizeof(f)); }
	
	void Insert(int x) {
		for (; x <= t; x += x & -x)
			++f[x];
	}
	
	int Query(int x) {
		int res = 0;
		for (; x; x -= x & -x)
			res += f[x];
		return res;
	}
} Bit;

int main() {
	freopen("running.in", "r", stdin);
	freopen("running.out", "w", stdout);
	scanf("%d%I64d%d", &n, &l, &c);//人数、圈数、一圈长度 
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i].speed);
	sort(a + 1, a + n + 1);
	Vmax = a[n].speed;
	for (int i = 1; i <= n; ++i)
		tr[i] = a[i].rank = l * a[i].speed % Vmax;
	sort(tr + 1, tr + n + 1);
	t = unique(tr + 1, tr + n + 1) - tr - 1;
	for (int i = 1; i <= n; ++i)
		a[i].rank = lower_bound(tr + 1, tr + t + 1, a[i].rank) - tr;
	for (int i = 1; i <= n; ++i) {
		ll cur = l * a[i].speed / Vmax;
		ans += cur * (i - 1) - sum - (i - 1) + Bit.Query(a[i].rank);//这里的树状数组正好维护的信息反了，它维护的是有多少个Yj<=Yi,所以用i-1减去它就可以了。
		sum += cur;
		Bit.Insert(a[i].rank);
	}
	cout << ans << endl;
	fclose(stdin); fclose(stdout);
	return 0;
}