0458. Poor Pigs

题目信息

题号:

0458

难度:

Hard

主题:

唯一有毒桶、并行测试、死亡时间、最少实验对象

原题:

LeetCode 0458

重点:

只有一个桶有毒、每轮可让猪饮用多个桶的混合样本、死亡结果可编码状态、必须在总时限内唯一定位

题目重述

有 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)。