题目链接

英文链接：https://leetcode.com/problems/poor-pigs/

中文链接：https://leetcode-cn.com/problems/poor-pigs/

题目详述

有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。

问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？

回答这个问题，并为下列的进阶问题编写一个通用算法。

进阶:

假设有 n 只水桶，猪饮水中毒后会在 m 分钟内死亡，你需要多少猪（x）就能在 p 分钟内找出 “有毒” 水桶？这 n 只水桶里有且仅有一只有毒的桶。

提示：

可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 m 分钟的冷却时间。在这段时间里，只允许观察，而不允许继续饮水。
任何给定的桶都可以无限次采样（无限数量的猪）。

题目详解

首先考虑一个相对简单的问题：

有 100 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 1 分钟内死去。如果需要你在 1 分钟内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？

答案是 7，因为 2^7 >= 100，最少需要 7 个二级制位数才能表示 0~99。二进制表示从 0000000 到 01100011。
让第一支猪饮用所有第一个二进制位为 1 的桶，让第二支猪饮用所有第二个二进制位为 1 的桶，依此类推。

上面是 buckets == 100 的情况。

其实，这个问题最简单的情况如下：

有 1 个桶，则需要 0 只猪，2^0 >= 1（就是这个桶里有毒，不需要猪）。
有 2 个桶，则需要 1 只猪，2^1 >= 2。
有 3 个桶，则需要 2 只猪，2^2 >= 3。
有 4 个桶，则需要 2 只猪，2^2 >= 4。下面详细阐述这种情况。
- 让第一支猪 A 饮用所有第一个二进制位为 1 的桶，即 1 号桶和 3 号桶，二进制分别为 01 和 11）。
- 让第二支猪 B 饮用所有第二个二进制位为 1 的桶，即 2 号桶和 3 号桶，二进制分别为 10 和 11）。
- 如果 A 死、B 死，说明是 3 号桶有毒。
- 如果 A 死、B 没死，说明是 1 号桶有毒。
- 如果 A 没死、B 死，说明是 2 号桶有毒。
- 如果 A 没死、B 没死，说明是 4 号桶有毒。
上面的这种问题是猪有 2 个状态，死或没死，所以它采用的是二进制。
那么对于“小猪喝了毒药，它会在 15 分钟内死去；在一小时内求得结果”这种情况，则此时猪有 5 种状态：15 分钟之后死，30 分钟之后死，45 分钟之后死，60 分钟之后死，没死。这样表示是因为如果猪没死，并且不超过规定时间则这头猪可以重用。此时应该采用 5 进制。所以答案就是找到最小的一个 n，满足 5^n >= buckets。
对于死亡时间为 minutesToDie、要求时间为 minutesToTest 的情况，此时猪有 minutesToTest / minutesToDie + 1 种状态，记为 base。找到最小的一个 n，满足 base^n >= buckets。
时间复杂度为 log(n)，准确地说对数的底为 base，而不是 2。

public class LeetCode_00458 {

    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int base = minutesToTest / minutesToDie + 1;
        int res = 0;
        int p = 1;
        while (p < buckets) {
            p *= base;
            ++res;
        }
        return res;
    }
}