arrays - 计算 k 分钟后将发生的交换次数的程序

Question

给定 n 名运行者在圆形跑道上运行。每个运行者穿过另一个运行者时，他们交换 gem 。给定每个运行者完成圆形跑道所用时间(以分钟为单位)的数组和一个整数 k。我们需要找到在过去 k 分钟之前将发生的交换次数。

[编辑 1]:我想过使用所有数字的 hcf 作为会面点，但无法通过。任何帮助都会很好。

Answer 1

我们在这里要做的是计算一个运行者超过另一个运行者的次数。首先，我们可以按速度对运行者进行排序，这稍后会派上用场。对于第 i 名运行者，我们可以很容易地计算出他们要跑的圈数，我将其称为 L(i)。对于两个运行者 i 和 j，其中 i 比 j 快，i< 的次数 将通过 j 是 floor(L(i) - L(j))。我们的解决方案是所有 i 和 j 对的这个值的总和，其中 i > j。

如果 n 的限制足够小，您可以遍历所有这些对并在 O(n^2) 时间内对值求和。但是如果 n 很大，这会太慢。如果我们只是想计算所有 i > j 的 L(i) - L(j) 的总和而不使用 floor 函数，我们可以在线性时间内完成此操作使用前缀和。

如果我们的运行者按照速度顺序从 0 到 n - 1 编号，对于 i 的每个值，L(i ) - L(j) 对于小于 i 的 j 的所有值等于 L(i) * i - P(i - 1 ))，其中 P(j) 是 L(0) + L(1) + L(2) + ... + L 之和的预计算值(j)。现在我们需要处理 floor 函数。对于两个实数 x 和 y，其中 x > y，floor(x - y) 等于 floor(x) - floor(y) 如果 x 的小数部分大于或等于 y 的小数部分，并且 floor(x) - floor(y) - 1 否则。

因此，如果我们需要计算一个运行者 i 超过另一个运行者的次数，我们可以首先使用上面描述的前缀和技术计算值，每个 L 值，然后减去 j 值的个数，其中 L(j) 的小数部分大于 L(i)< 的小数部分。查找 L(j) 的小数部分大于 L(i) 的小数部分的 j 值的个数基本上是 inversion counting实数，这可以用二叉索引树来完成。

最终的复杂度是O(n log n)。