Yandex节目竞赛:警报

Question

在比赛中，我试着解决了这个问题，但我所有的尝试都超过了时限。我试着用Min-堆来解决这个问题，但不能通过所有的测试。如何在给定的时间和空间要求内解决这一问题？

Problem语句程序员Alexey喜欢晚上工作，不喜欢迟到。为了准确地在早上醒来，亚历克西每天晚上都会在他的手机上启动N闹钟。每个闹钟的排列方式使它从打开闹钟的时间起，每隔一分钟就响一次。例如，如果闹钟是在时间t_i的时刻启动的，那么它就会在t_i, t_i + X, t_i + 2 * X等时刻响起来。此外，如果某两个警报器一次响起，则只显示其中一个。众所周知，在醒来之前，亚历克西每天早上都会听准确的K闹钟，然后醒来。确定亚历克斯醒来的时间点。Input格式输入格式第一行包含三个整数。N, X和K (1 ≤ N ≤10^5, 1≤X, K≤10^9) --警报的数量、呼叫的频率以及需要关闭的警报数量，才能让Alex醒来。第二行包含N个整数--输入闹钟的时间点。要求时间限制:2秒内存限制:256 In 示例示例1输入6 5 10 1 2 3 4 5 6输出10示例2输入5 7 12 5 22 17 13 8输出27备注在第二个示例中有5个闹钟，频率为7次。例如，第一个闹钟会在5、12、19、26、33等时间响。如果你同时看所有的闹钟，它们会在下列时间响: 5，8，12，13，15，17，19，20，22 (同时有第2和第5闹钟)，24，26，27，29，…。。在12号打电话时，亚历克西必须醒过来，这与时间27的时间点相对应。

My解决方案

归类为“超过时限”

import heapq


def main():
    n, x, k = map(int, input().split(" "))
    times = list(map(int, input().split(" ")))

    heapq.heapify(times)

    answers = []

    while k:
        v = heapq.heappop(times)
        heapq.heappush(times, v + x)

        if len(answers) == 0 or answers[len(answers)-1] != v:
            answers.append(v)
            k -= 1

    print(answers[k-1])


if __name__ == "__main__":
    main()

Answer 1

并非所有计数问题都需要枚举正在计数的项目。如果您被要求计算总共有多少只羊，如果有n卡车，每个卡车上都有k绵羊，那么您可以这样写：

total_sheep = 0
for truck in range(n):
    for sheep in range(k):
        total_sheep += 1

或者你可以切入到追逐中，并计算它为：

total_sheep = n * k

你试图解决的问题更微妙，但也可以以类似的方式攻击。模算法会成为你做这件事的朋友。与其将设置时间看作单个数字，不如在除以(quotient, remainder)后将其转换为X的元组。这将例如将第二个示例的时间列表转换为：

 5 --> (0, 5)
22 --> (3, 1)
17 --> (2, 3)
13 --> (1, 6)
 8 --> (1, 1)

我们可以使用这些信息来删除警报列表:如果任何两个警报都有相同的剩余，它们将同时响，所以我们只需要保持较小的警报。这将在对列表进行排序之后，将其转换为：

 5 --> (0, 5)
 8 --> (1, 1)
13 --> (1, 6)
17 --> (2, 3)

这两个数字告诉我们，在X分钟的哪个时段里，警报第一次响起，在什么情况下，警报第一次响起。这样我们就可以按顺序处理它，并知道：

• 在第一(0)期结束时，第一次发出了1次警报，以后每段时间总共会发出1次警报，发出的警报总数也是1次。
• 在第二(1)期结束时，第一次响起两个警报，随后每段时间发出三个警报，发出的警报总数为4个。
• 在第三(2)期结束时，一个新的警报已经响起，4个警报将在每一周期发出，总共有8个警报已经响起。

由于没有更多的警报需要处理，到目前为止，我们有8个警报，每个警报周期多4个，并且希望达到12个，一些简单的数学告诉我们，这将发生在第四个(3)阶段，它将是最后一个警报将到达它。

为了让数学更清楚，让我们想象一下，我们想要总共达到14个警报。既然8已经响了，我们还有14 -8=6.由于每段时间会发出4个警报，而6的商数和其余的除以4是1和2，我们知道我们将在一个完整的周期后达到我们的目标，再加上下一阶段的4个警报中的2个。这将转换为4个完整的时间段，再加上该期间的第二次警报发出的时间。4个完整周期的时间为7*4= 28。我们需要添加第二个when的偏移量，根据偏移量对它们进行排序，而不是按开始时间排序，所以我们需要添加3，而不是1，最终结果是31。

这个总体大纲省略了许多可怕的细节，比如在处理完列表之前，如果我们到达警报的目标数量，该怎么办。而且上面描述的数学在所有的情况下都是很难正确的，因为有很多错误的机会。我不会因为编写代码而破坏你的乐趣:试一试，我很乐意回顾你的下一个版本。

Answer 2

Min堆方法似乎是正确的。问题在于answers。它可能会变得相当大(直到10^9)。由于它的增长，所有的重新分配都是非常昂贵的。

但是你根本不需要它。你只关心最近一次警报的时间。只有一个价值：

    while k:
        v = heapq.heappop(times)
        heapq.heappush(times, v + x)

        if last_alarm != v:
            last_alarm = v
            k -= 1

也就是说，访问列表的最后一个元素的一种惯用方法是answers[-1]。