可怜的小猪

标签: 数学 动态规划 组合数学

难度: Hard

有 buckets 桶液体，其中 正好有一桶 含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

  1. 选择若干活猪进行喂养
  2. 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
  3. 小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
  4. 过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
  5. 重复这一过程，直到时间用完。

给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回 在规定时间内判断哪个桶有毒所需的 最小 猪数 。

示例 1：

输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出：5

示例 2：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
输出：2

示例 3：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 30
输出：2

提示：

  • 1 <= buckets <= 1000
  • 1 <= minutesToDie <= minutesToTest <= 100

Submission

运行时间: 20 ms

内存: 16.1 MB


class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:


        # 可以尝试的次数
        radix = (minutesToTest // minutesToDie) + 1

        # x^radix>=buckets
        x = 0
        while radix**x < buckets:
            x += 1
        return x

Explain

这个题目可以用进制转换的思想来解决。我们可以把每头猪看作一个 radix 进制的数位，其中 radix 是在规定时间内可以进行的测试次数加 1。每头猪可以代表 0 到 radix-1 这 radix 种状态。如果有 x 头猪，它们一共可以表示 radix^x 种组合。我们只需要找到最小的 x，使得 radix^x >= buckets 即可。

时间复杂度: O(log(buckets))

空间复杂度: O(1)

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        # 可以尝试的次数
        radix = (minutesToTest // minutesToDie) + 1
        
        # x^radix >= buckets
        x = 0
        while radix**x < buckets:
            x += 1
        return x

Explore

进制转换思想在此问题中非常适用，因为它允许我们通过最小化猪的数量来最大化信息的获取。每只猪代表一个数位，其状态数等于它可能存活到的测试轮数加一（存活或某一轮后死亡）。这种方法通过每只猪的不同存活状态来编码不同的水桶，有效地将问题转化为一个信息编码问题。这种方法被选择是因为它直接、高效并且能够精确地解决问题，其他算法如穷举等可能需要更多资源且效率较低。

计算进制基数 `radix` 时，将 `minutesToTest` 除以 `minutesToDie` 是为了确定在总测试时间内可以进行多少轮完整的测试。加一的逻辑是因为每只猪在测试期间不仅可以在某一轮后死亡的各种情况中的一种，还可以完全不死亡。例如，如果可以测试3轮，则每只猪可以在第1轮、第2轮、第3轮死亡，或者完全不死亡，共4种状态，因此 `radix` 是测试轮数加一。

题解中已经考虑了一只或多只猪死亡的情况。每只猪的死亡代表了一种信息，即某一桶水是有毒的。通过不同的猪在不同时间点的死亡组合，我们可以确定具体哪一桶水是有毒的。因此，猪的死亡是解决问题的关键部分，而不是一个未考虑的副作用。这种方法确保了即使有猪死亡，也可以准确地判断出哪一桶水有毒。

在这个问题中，`x` 代表需要的猪的数量。`radix**x >= buckets` 表示通过这些猪可以用来区分的不同状态组合必须足够多，至少要能覆盖所有水桶的数量。这样，每一种特定的猪的存活与死亡组合就可以对应到一桶特定的水。因此，`x` 直接影响了实验的设计，即需要多少只猪来确保可以在给定的测试轮数内找出哪一桶水是有毒的。