leetcode - 猪喝水的问题 - 《数据结构与算法》

leetcode 458

leetcode 458

链接：https://leetcode-cn.com/problems/poor-pigs/

解题代码：

/**
 * @param {number} buckets
 * @param {number} minutesToDie
 * @param {number} minutesToTest
 * @return {number}
 */
var poorPigs = function(buckets, minutesToDie, minutesToTest) {
//每只小猪最多可以尝试的次数
    const n = minutesToTest / minutesToDie + 1;
    let allPoss = Math.log(buckets)/Math.log(n);
    return Math.ceil(allPoss)
};

解题思路：
只有一只水桶有毒，所以比较容易得出水桶有毒的状态就是水桶的数量。

那么需要抽象出一只猪在规定时间内可以喝水几次，因为有毒喝了会死，所以总状态数也是喝水次数。

因为多头猪可多进程的执行判断喝水，所以他们之间是乘方的关系，我们所需要知道的仅仅是有多少猪的乘方可以满足大于等于水的总状态即可。

把水每次都均分到多个进程里，然后利用排除法，当出现猪死亡的时候，就能够利用进程之间的排除法发现是哪个桶有毒。因为每个进程里分到的水桶数都标有它被分配到的另一个猪的位置信息，能够帮忙排除毒是不是因为当前桶有毒引起的。