LeetCode 458. 可怜的小猪
目录
题目描述
题意分析
题目目标：有 buckets 桶液体，其中恰好一桶有毒。猪喝下有毒液体后会在 minutesToDie 分钟后死亡，总共只有 minutesToTest 分钟的测试时间，问最少需要多少头猪才能保证在时限内确定是哪一桶有毒。
核心约束：题目要的是「保证」，也就是最坏情况下也必须能分辨出来，这排除了任何依赖运气的方案。允许一头猪同时喝多桶、也允许多头猪喝同一桶，这两条自由度是解法成立的前提——如果每头猪只能喝一桶，答案就退化成 buckets - 1，题目也就没意思了。两个时间参数只以商的形式出现在答案里，说明真正有意义的量是「能做几轮测试」而不是具体的分钟数。数据范围里 buckets 可达 1000，而单头猪的分辨能力随轮数指数增长，所以答案会非常小。
边界处理：buckets 为 1 时无需测试，答案是 0；minutesToTest 可能小于 minutesToDie，此时一轮都做不了，每头猪只能提供「活着」这一种结果，无法区分任何东西——好在这种情形下题目保证 buckets 为 1；轮数 T 由整数除法得到，余下的零头时间不足以完成一次完整观察，必须向下取整；连乘计算 $(T+1)^p$ 时可能超出 int，用 64 位承接更稳妥。
解法：信息量分桶
核心思路
设可完成的测试轮数为
\[rounds=\left\lfloor\frac{minutesToTest}{minutesToDie}\right\rfloor\]一头猪有
\[(rounds+1)^p\ge buckets\]rounds + 1种可区分结果：在某一轮后死亡，或测试结束仍存活。若有p头猪，联合结果数为 $(rounds+1)^p$，要区分每个可能的毒桶，必须满足这不仅是下界，也能达到。把桶编号写成
rounds + 1进制，每头猪负责一位；该位的数字决定它在哪一轮饮用，另留一个数字表示始终不饮用。最终每头猪的死亡轮次或存活状态恰好还原该位，联合状态唯一确定毒桶。因此只需从容量 1 开始，每增加一头猪就乘以单猪状态数，第一次覆盖
buckets时停止。容量使用 64 位，避免连续乘法溢出。
解题步骤
- 用整数除法计算完整测试轮数，再令
states = rounds + 1。- 初始化
pigs = 0、capacity = 1。- 当容量小于桶数时，乘以
states并增加一头猪。- 返回首次满足容量要求的
pigs。
buckets = 1000, minutesToDie = 15, minutesToTest = 60时，每头猪有 5 种状态；容量依次为 1、5、25、125、625、3125，所以需要 5 头猪。
buckets = 1时初始容量已经足够，返回 0；容量恰好等于桶数时也必须立即停止。
代码实现
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(\log_{states} buckets)$，循环次数就是答案。
- 空间复杂度：$O(1)$。
关键点总结
- 单头猪的信息量是死亡轮次加“始终存活”，共
rounds + 1种状态。p头猪能编码states^p种联合结果，必须覆盖所有桶。- 信息量下界还需用进制编号方案证明可达。
- 不足一个致死周期的剩余时间不能形成新状态。
- 使用整数容量迭代比浮点对数更稳妥。
易错点总结
- 忘记“存活”状态会把单猪容量从
rounds + 1错算为rounds。- 容量循环使用
<=会在恰好覆盖所有桶时多加一头猪。- 容量从
states开始会使buckets = 1错误返回 1；零头猪的初始容量是 1。- 测试轮数向上取整会使用无法在时限内观察结果的轮次。
- 浮点对数在整数幂边界可能产生取整误差，直接整数累乘更可靠。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 887. 鸡蛋掉落 | 困难 | 探测是串行自适应的，后续决策依赖前次结果，必须用动态规划而非一次性编码 |
| 374. 猜数字大小 | 简单 | 同为信息论下界为 $\log$ 的探测问题，但每次只能获得一比特且必须串行 |
| 319. 灯泡开关 | 中等 | 同样禁止模拟、要求直接推出闭式答案，依据是约数个数的奇偶性 |
| 299. 猜数字游戏 | 中等 | 反馈信息更丰富，重点在如何把一次观测拆解成公牛与奶牛两类计数 |
| 面试题 16.10. 生存人数 | 中等 | 同样把连续的时间量离散成有限个可统计的事件点再做计数 |