arrays - 程序找出在 k 分钟过去之前将发生的交换次数

Question

给定 n 个在圆形轨道上运行的跑步者。每个跑步者在跨越另一个跑步者时，他们交换宝石。给定一个包含每个跑步者完成循环轨道所用时间（以分钟为单位）的数组和一个整数 k。我们需要找出在 k 分钟过去之前将发生的交换次数。

[编辑 1]：我认为使用所有数字的 hcf 作为会面点，但无法通过。你能帮忙的话，我会很高兴。

标签： arraysalgorithm

Answer 1

我对这类问题的回答通常是先自己尝试一下，但这是一个非常困难的问题，所以我要给你解决方案。

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

如果限制n足够小，您可以遍历所有这些对并及时总结这些值O(n^2)。但是如果n很大，这将太慢。如果我们只是想在没有底函数的情况下计算L(i) - L(j)所有的总和i > j，我们可以使用前缀总和在线性时间内完成。

如果我们的跑步者n - 1按照他们的速度顺序从 0 到编号，对于 的每个值，所有小于的值的i总和等于，其中是总和的预计算值。现在我们需要处理地板功能。对于两个实数，其中，如果 的小数部分大于或等于 的小数部分，则等于，否则。L(i) - L(j)jiL(i) * i - P(i - 1))P(j)L(0) + L(1) + L(2) + ... + L(j)xyx > yfloor(x - y)floor(x) - floor(y)xyfloor(x) - floor(y) - 1

因此，如果我们需要计算一个跑步者i超过另一个跑步者的次数，我们可以首先使用上面描述的前缀和技术计算每个L值的下限，然后减去j小数部分L(j)大于的值的数量的小数部分L(i)。找到j小数部分L(j)大于小数部分的值的数量L(i)基本上是对实数进行倒数计数，这可以通过二叉索引树来完成。

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