458. 可怜的小猪

Hard

题目描述

有 buckets 桶液体，其中 恰好有一桶 是有毒的。为了弄清楚哪一桶是有毒的，你可以喂一些猪喝，看看它们是否会死掉。不幸的是，你只有 minutesToTest 分钟来确定哪桶液体是有毒的。

喂猪的规则如下：

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

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

示例 1：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
输出：2
解释：我们可以按照如下方式来判断哪个桶是有毒的：
在时间 0，让第一只猪喝桶 1 和桶 2，第二只猪喝桶 2 和桶 3。
在时间 15，会有如下四种可能的结果：
- 如果只有第一只猪死了，那么桶 1 一定是有毒的。
- 如果只有第二只猪死了，那么桶 3 一定是有毒的。
- 如果两只猪都死了，那么桶 2 一定是有毒的。
- 如果两只猪都没死，那么桶 4 一定是有毒的。

示例 2：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 30
输出：2
解释：我们可以按照如下方式来判断哪个桶是有毒的：
在时间 0，让第一只猪喝桶 1，让第二只猪喝桶 2。
在时间 15，会有如下两种可能的结果：
- 如果任何一只猪死了，那么死了的猪喝的桶一定是有毒的。
- 如果两只猪都没死，那么让第一只猪喝桶 3，让第二只猪喝桶 4。
在时间 30，一定有一只猪会死，死了的猪喝的桶一定是有毒的。

提示：

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

解题思路

这是一个非常巧妙的数学问题，关键在于理解每只猪能提供的信息量。

核心思路：

• 首先计算测试轮数：tests = minutesToTest / minutesToDie
• 每只猪在整个测试期间可以有 tests + 1 种状态：
  • 在第0轮死亡、第1轮死亡、…、第tests轮死亡，或者始终存活
  • 这给我们 tests + 1 种不同的信息状态

信息理论分析：

• 如果我们有 x 只猪，每只猪有 tests + 1 种可能状态
• 那么总共可以区分 (tests + 1)^x 种不同情况
• 要识别 buckets 个桶中的毒桶，我们需要 (tests + 1)^x >= buckets

编码策略： 我们可以把这个问题想象成一个 (tests + 1) 进制的数字系统。每只猪代表一个位数，猪的死亡时间点代表该位的数值。通过这种方式，我们可以用最少的猪数来唯一标识每个桶。

算法步骤：

1. 计算测试轮数 tests = minutesToTest // minutesToDie
2. 计算每只猪的状态数 states = tests + 1
3. 找到满足 states^pigs >= buckets 的最小猪数

这个解法的时间复杂度是 O(log(buckets))，空间复杂度是 O(1)。

代码实现

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        int states = tests + 1;
        int pigs = 0;
        
        while (pow(states, pigs) < buckets) {
            pigs++;
        }
        
        return pigs;
    }
};

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        tests = minutesToTest // minutesToDie
        states = tests + 1
        pigs = 0
        
        while states ** pigs < buckets:
            pigs += 1
            
        return pigs

public class Solution {
    public int PoorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int tests = minutesToTest / minutesToDie;
        int states = tests + 1;
        int pigs = 0;
        
        while (Math.Pow(states, pigs) < buckets) {
            pigs++;
        }
        
        return pigs;
    }
}

var poorPigs = function(buckets, minutesToDie, minutesToTest) {
    const tests = Math.floor(minutesToTest / minutesToDie);
    const states = tests + 1;
    let pigs = 0;
    
    while (Math.pow(states, pigs) < buckets) {
        pigs++;
    }
    
    return pigs;
};

复杂度分析