gyro永不抽风

ああああああああああああああああおおおおおおおおおおおおおおおお

310-01-ACOJ-0864-奶牛赛跑

310-01-ACOJ-0864 : 奶牛赛跑

题目大意:

有$n$头奶牛,在一个圆形的赛跑场地里赛跑。所有奶牛同时从起点出发,奶牛的速度都是匀速的,其中第$i$头牛的速度为$v_i$,跑道的长度为单位$1$。当跑得最快那头奶牛跑完$k$圈之后,比赛就结束了。

有时候,跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈,从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中,套圈事件一共会发生多少次呢?

题解:

对于这道题,很显然可以直接求解(小学问题),然后要考虑的是如何降低计算的时间复杂度(原来是$O(n^2)$。

由于每一个奶牛的追击追击次数可以显然得到:$\lfloor \frac {(v_i - v_j)}{v}k\rfloor$,所以要求的就是$\sum_{1≤j<i≤n}\lfloor\frac {v_i - v_j}{v}k\rfloor$。

那么采用整数与小数分离的思想计算:(对于负数向下取整是更小,所以对于$-0. ~…$向下取整为$-1$)

而可以发现$\sum_{1≤j<i≤n} \lfloor \alpha_i - \alpha_j\rfloor$就是求$\alpha$序列的逆序对个数。

而对于求逆序对同样可以进行优化(因为小数求逆序对需要进行离散化,很烦),令$\alpha_i’ = v_i \times k \mod v_n$,这非常好证明。

正解:

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
#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

int n, k;
const int maxn = 1000005;
int v[maxn];
int A[maxn], a[maxn];

struct node {
int id, val;
} B[maxn];

int T[maxn];

int lb(int i) { return i & (-i); }

bool cmp(node a, node b) {
if (a.val == b.val) return a.id < b.id;
return a.val < b.val;
}

void add(int i, int d) {
while (i <= n + 100) {
T[i] += d;
i += lb(i);
}
}

int sum(int i) {
int ans = 0;
while (i > 0) {
ans += T[i];
i -= lb(i);
}
return ans;
}

signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> v[i];
sort(v + 1, v + 1 + n);
int ans = 0;
for (int i = 1; i <= n; i ++) {
A[i] = v[i] * k / v[n]; a[i] = v[i] * k % v[n];
ans += (2 * i - 1 - n) * A[i];
B[i] = (node) {i, a[i]};
}
sort(B + 1, B + 1 + n, cmp);
// for (int i = 1; i <= n; i ++) cout << B[i].id << " " << B[i].val << endl;
for (int i = 1; i <= n; i ++) {
int p = sum(B[i].id - 1);
ans -= (i - 1 - p);
add(B[i].id, 1);
}
cout << ans << endl;
return 0;
}
__EOF__
-------------本文结束感谢您的阅读-------------

本文标题:310-01-ACOJ-0864-奶牛赛跑

文章作者:gyro永不抽风

发布时间:2020年03月01日 - 22:03

最后更新:2020年09月22日 - 20:09

原始链接:http://gyrojeff.moe/2020/03/01/310-01-ACOJ-0864-%E5%A5%B6%E7%89%9B%E8%B5%9B%E8%B7%91/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 转载请保留原文链接及作者!

真的不买杯奶茶吗?T^T

欢迎关注我的其它发布渠道