Archived | 310-01-ACOJ-0864-奶牛赛跑
Archived | 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 ）
$$
\begin {align*}
&\frac {(v_i-v_j)} {v} k = A + \alpha \
\Rightarrow~&\frac {v_ik}v - \frac {v_jk}v = A_i + \alpha_i - (A_j + \alpha_j) _
\Rightarrow~&\sum{1≤j<i≤n}\lfloor\frac {v_i - vj}{v}k\rfloor = \sum{1≤j<i≤n}(A_i - Aj)+\sum{1≤j<i≤n}\lfloor\alpha_i - \alpha_j\rfloor _
&\sum{1≤j<i≤n}(A_i - A_j) _
=~&\sum{1≤i≤n}(i - 1)A_i - (n - i)A_i = \sum{1≤i≤n}(i - 1 - n + i) A_i = \sum{1≤i≤n}(2i - 1 - n)A_i \
\end {align*}
$$
而可以发现\sum_{1≤j<i≤n} \lfloor \alpha_i - \alpha_j\rfloor$``$\alpha 序列的逆序对个数。
而对于求逆序对同样可以进行优化（因为小数求逆序对需要进行离散化，很烦），令\alpha_i’ = v_i \times k \mod v_n ，这非常好证明。
正解：
#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;
}
本文作者：博主： gyrojeff 文章标题：Archived | 310-01-ACOJ-0864-奶牛赛跑
本文地址：https://cloud.tencent.com/developer/article/1827238
版权说明：若无注明，本文皆为“gyro永不抽风！”原创，转载请保留文章出处。
许可协议:署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 转载请保留原文链接及作者！
我的博客即将同步至腾讯云+社区，邀请大家一同入驻