310-01-ACOJ-0864 : 奶牛赛跑
题目大意：
有n 头奶牛，在一个圆形的赛跑场地里赛跑。所有奶牛同时从起点出发，奶牛的速度都是匀速的，其中第i 头牛的速度为v_i ，跑道的长度为单位1 。当跑得最快那头奶牛跑完k 圈之后，比赛就结束了。
有时候，跑得快的奶牛可以比跑得慢的奶牛多绕赛场几圈，从而在一些时刻超过慢的奶牛。这就是最令观众激动的套圈事件了。请问在整个比赛过程中，套圈事件一共会发生多少次呢？
题解：
对于这道题，很显然可以直接求解（小学问题），然后要考虑的是如何降低计算的时间复杂度（原来是O(n^2) 。
由于每一个奶牛的追击追击次数可以显然得到：lfloor frac {(v_i - v_j)}{v}krfloor ，所以要求的就是sum_{1≤j<i≤n}lfloorfrac {v_i - v_j}{v}krfloor
那么采用整数与小数分离的思想计算：（对于负数向下取整是更小，所以对于-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}lfloorfrac {v_i - vj}{v}krfloor = sum{1≤j<i≤n}(A_i - Aj) sum{1≤j<i≤n}lflooralpha_i - alpha_jrfloor _
&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_jrfloor$``$alpha 序列的逆序对个数。
而对于求逆序对同样可以进行优化（因为小数求逆序对需要进行离散化，很烦），令alpha_i’ = v_i times k mod v_n ，这非常好证明。
正解：
代码语言：javascript复制#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) 转载请保留原文链接及作者！
我的博客即将同步至腾讯云 社区，邀请大家一同入驻
