0458. Poor Pigs¶
题目信息¶
- 题号:
0458
- 难度:
Hard
- 主题:
唯一有毒桶、并行测试、死亡时间、最少实验对象
- 原题:
- 重点:
只有一个桶有毒、每轮可让猪饮用多个桶的混合样本、死亡结果可编码状态、必须在总时限内唯一定位
题目重述¶
有 buckets 个液体桶,其中恰好一个有毒。猪喝到毒液后会在 minutesToDie 分钟内死亡;总测试时间为 minutesToTest。在每轮开始时,可以让每只猪饮用任意若干桶的混合样本,并根据各轮结束时猪是否死亡来判断毒桶。
返回在规定时间内保证唯一找出有毒桶所需的最少猪数。buckets 位于 [1, 1000],并满足 1 <= minutesToDie <= minutesToTest <= 100。测试轮数为 floor(minutesToTest / minutesToDie);每只猪除了在某一轮死亡外,还可能直到测试结束仍存活。
自建示例¶
可以进行两轮测试:
输入:buckets = 16,minutesToDie = 15,minutesToTest = 30
输出:3
解释:可以进行 2 轮,每只猪有“第一轮死、第二轮死、最终存活”三种状态。两只猪只有 3^2 = 9 种组合,不足以区分 16 桶;三只猪有 27 种组合,因此最少为 3。
只有一个桶:
输入:buckets = 1,minutesToDie = 10,minutesToTest = 10
输出:0
解释:无需进行任何测试,唯一的桶已经确定是毒桶。
把每只猪看成一个多进制状态位¶
可进行的完整测试轮数为 rounds = minutesToTest / minutesToDie。一只猪有 rounds + 1 种可观察状态:在第 1、2、……轮死亡,或一直存活。若有 p 只猪,联合观察结果最多编码 (rounds + 1)^p 个桶;要唯一定位毒桶,必须让这个数量至少覆盖 buckets。
每轮给不同猪安排不同的桶组合,就相当于为桶编号的每一位设置该猪的状态。因而找到满足容量条件的最小 p 即得到最少猪数。
C++ 实现¶
class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int rounds = minutesToTest / minutesToDie;
long long states = rounds + 1;
long long distinguishable = 1;
int pigs = 0;
while (distinguishable < buckets) {
distinguishable *= states;
++pigs;
}
return pigs;
}
};
代码分析¶
死亡轮次和存活状态共同构成一只猪的离散观测值;多只猪的状态组合数相乘,所以最小猪数是最小的满足幂次覆盖桶数的指数。容量为 1 时循环不执行并返回 0。时间复杂度为 O(log_{rounds+1} buckets),额外空间复杂度为 O(1)。