你们抵制996，但工作量完不成，不加班怎么办？

简单说，就是有一堆桶，其中有一桶装着毒药，我们要在有限的时间内通过喂猪喝水的实验，确定是哪一桶。题目给了几个关键参数：

• buckets ：桶的总数。
• minutesToDie ：猪喝到毒药后会死亡所需的时间。
• minutesToTest ：我们总共有多少时间来做实验。

我们的目标是最小化实验中需要的小猪数量，同时保证能准确找出哪一桶是毒药。

这道题目乍一看有点懵，觉得怎么能用最少的小猪解决问题呢？我们先来理清几个核心点：

1. 小猪可以多次测试，每次测试后根据其存活或死亡的情况来获取信息。
2. 小猪喝水的方式决定了我们能够获取的信息量。比如，一个猪一次测试有两种可能性：存活或者死亡。
3. 我们需要利用猪的死亡和存活状态，将桶分组，并通过组的状态唯一确定哪一桶含毒。

换句话说，这题的核心在于如何利用小猪的状态构建一种“信息编码方式”，以最少的小猪数找到毒药桶的位置。

推导最少小猪数量

时间周期和状态数量： 一个猪在 minutesToTest 内可以测试的轮次是： rounds = minutesToTest / minutesToDie （向下取整）。在每轮测试中，一个猪的状态可以分为两种：活着或者死了。如果我们有多头猪，每头猪的状态组合会呈现指数增长。

状态数量公式： 对于 n 头猪和 rounds 轮测试，总的状态数量为 (rounds + 1)^n 。这里的 (rounds + 1) 表示每头猪有多少种可能的状态（活或者死）， n 表示我们有多少头猪。

找到毒药桶的数量： 我们需要通过这些状态区分所有的桶，也就是说，状态的总数需要覆盖 buckets ，即：

(rounds + 1)^n >= buckets

然后，我们通过公式解出最小的 n ：

n = ceil(log(buckets) / log(rounds + 1))

有了公式后，接下来看代码如何实现：

public class PoorPigs {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        // 计算最多可以测试的轮数
        int rounds = minutesToTest / minutesToDie;
        // 每头猪的状态数
        int states = rounds + 1;
        // 猪的数量
        int pigs = 0;
        
        // 利用公式计算最小需要的猪数量
        while (Math.pow(states, pigs) < buckets) {
            pigs++;
        }
        
        return pigs;
    }

    public static void main(String[] args) {
        PoorPigs solution = new PoorPigs();
        System.out.println(solution.poorPigs(1000, 15, 60)); // 输出示例
    }
}

代码解析

1. 首先计算 rounds ，表示在给定时间内能测试的轮数。
2. states 表示每头猪的状态数（死亡或存活）。
3. 使用 Math.pow 来计算 (rounds + 1)^pigs ，并通过循环找到满足公式的最小 pigs 。
4. 返回 pigs ，即所需的小猪数。

假设有 1000 桶水， minutesToDie 为 15 分钟， minutesToTest 为 60 分钟：

• 我们有 rounds = 60 / 15 = 4 次测试机会。
• 每头猪有 rounds + 1 = 5 种状态。
• 要覆盖 1000 个桶，我们需要找到最小的 pigs ，使得 5^pigs >= 1000 。