LeetCode 458. 可怜的小猪

约 3 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
动态规划 数学 组合数学

题目描述

✅ 458. 可怜的小猪

image-20260929100714948

image-20260929100715063

题意分析

buckets 桶液体中恰好一桶有毒。每轮可以让活猪同时喝任意多桶液体，等待 minutesToDie 分钟后，喝到毒药的猪死亡。要在 minutesToTest 分钟内确定毒桶，求最少需要几头猪。

解法：状态计数 + 整数容量累乘

核心思路

[!blue]

可完成的完整观察轮数为 rounds = minutesToTest / minutesToDie。一头猪的结果不只有生和死，还能区分第几轮死亡：第 1 轮到第 rounds 轮死亡，或测试结束仍存活，共有 states = rounds + 1 种结果。

p 头猪最多给出 states^p 种结果组合，每个毒桶都必须对应不同组合，因此必须满足 states^p >= buckets。否则至少两桶会产生相同观察结果，无法区分。

这个下界可以达到：给每桶分配一个不同的 states 进制编号，使用 p 位，每一位对应一头猪。把数字 0 约定为一直存活，数字 r 约定为第 r 轮死亡。在第 r 轮，让每头活猪喝下所有“对应位等于 r”的桶里的液体。若毒桶对应位为 r，这头猪此前不会接触毒液，恰好在这一轮死亡；对应位为 0 则一直喝不到毒液。最后所有猪的结果就能还原毒桶编号。

因此只需求让容量覆盖桶数的最小 p。从 0 头猪、容量 1 开始，每增加一头猪就把容量乘以 states，首次达到或超过桶数时停止，避免使用浮点对数处理整数边界。

解题步骤

  1. 计算完整轮数 rounds 和每头猪的状态数 states = rounds + 1。
  2. 初始化 pigs = 0、capacity = 1。
  3. 只要 capacity < buckets，就将容量乘以 states，并令 pigs++。
  4. 返回 pigs。只有一桶时无需实验，初始容量就足够，返回 0。

题目保证 minutesToDie <= minutesToTest，因此至少能观察一轮，states >= 2，容量会严格增长并最终满足条件。

代码实现

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int rounds = minutesToTest / minutesToDie;
        // 每轮死亡和始终存活分别形成可区分状态。
        int states = rounds + 1;

        int pigs = 0;
        // 零头猪只能表示一个结果，恰好覆盖单桶情形。
        long capacity = 1;

        while (capacity < buckets) {
            capacity *= states;
            pigs++;
        }

        return pigs;
    }
}

func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
    rounds := minutesToTest / minutesToDie
    // 每轮死亡和始终存活分别形成可区分状态。
    states := rounds + 1
    pigs := 0
    // 零头猪只能表示一个结果，恰好覆盖单桶情形。
    capacity := int64(1)
    for capacity < int64(buckets) {
        capacity *= int64(states)
        pigs++
    }
    return pigs
}

复杂度分析

  • 时间复杂度：$O(1+\log_{states}buckets)$，循环次数等于所需猪数。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 测试结束仍存活也是一个状态。
  • 状态数给出必要下界，按进制位安排喂水说明下界可达。
  • 不足一个完整观察周期的时间不能算新一轮。

易错点总结

[!yellow]

  • 漏掉存活状态：低估每头猪可区分的结果数。
  • 容量恰好相等仍继续循环：多算一头。
  • 轮数向上取整：使用了无法完成观察的轮次。

相似题目

题目 难度 关联与区别
887. 鸡蛋掉落 困难 同样按实验能区分的状态数量推导所需资源，原题受鸡蛋损坏影响，本题每只猪可表示死亡轮次或存活结果。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/78881051
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！