algorithm - 马桶座算法

Question

让我们来看看一个普通的房子，一个男人必须每 n 分钟上一次厕所，要求坐起来，还有一个女人，必须每 m 分钟，要求座位放下。是否有可能创建一个 O(1) 算法，该算法将在给定的 X 分钟内输出马桶座圈移动的确切次数？有两种不同的附加输入:
1. 男人总是在拜访后离开座位。
2. 男人总是在拜访后放下座位。

结论在现实生活中(涉及n远大于m，且X->无穷大)，证明一些座椅运动没有区别。
但是，如果男性比女性更频繁地这样做，那么如果他将座椅保持向上，将会延长座椅生命周期，但在这种情况下，他们中的一个(或两个)是否应该去看医生。< br/> 现在我知道什么对座椅本身最好，但哪个人的 Action 更多 - 是另一个问题(无论如何都不应该问)。

Answer 1

是的，有一个基本的 O(1) 算法。

我首先假设两个人都在 t=0 时开始“滴答作响”。 我相信该解决方案应该推广到不同的开始时间，但从时间线的一个“自由端”扩展到两端并不难。

假设 n <= m。

然后我们的时间轴看起来像这样(“x”表示“移动”，而不是访问)

  0     m    2m    ..              t-t%m  t
  +-----+-----+-----+-----+-----+-----+--o
W x     x     x     x     x     x     x 
M x  x    x    x       x     x    x     x?

所以，女人上楼 (t/m) 次，在 每次女人去——在半开区间(a*m,*m+m] -- 这个人至少走了一次，因此翻转了一次座位。为了 每次她每隔一段时间翻转一次座位，他也翻转一次。 不过，他以后可能会再去一次 她最后一次旅行，取决于他们的相对时间， 您可以根据 t 对它们各自的周期取模进行计算。

total_moves = floor(t/m) * 2 + (t%m < t%n ? 1 : 0)

现在对于 n > m 的情况。

男女角色互换……半开区间 [a<em>n, a</em>n+n)总是涉及两个 Action 。其余的 该行的行是 [t-t%n, t)，其中该人一开始就走了一次， (这是 +1 步，但我们在 t=0 时计算了两个人的 +2 步，我们可能应该丢弃它)如果女人的剩余时间等于或少于他，她就会离开

total_moves = floor(t/n) * 2 - 1 + (t%m >= t%n ? 1 : 0)