https://leetcode-cn.com/problems/poor-pigs/

题目

buckets 桶液体,其中 正好 有一桶含有毒药,其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药,你可以喂一些猪喝,通过观察猪是否会死进行判断。不幸的是,你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下:

选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水,并且该过程不需要时间。
小猪喝完水后,必须有 minutesToDie 分钟的冷却时间。在这段时间里,你只能观察,而不允许继续喂猪。
过了 minutesToDie 分钟后,所有喝到毒药的猪都会死去,其他所有猪都会活下来。
重复这一过程,直到时间用完。
给你桶的数目 bucketsminutesToDieminutesToTest ,返回在规定时间内判断哪个桶有毒所需的 最小 猪数。

思考

我其实见过类似的题,只不过那个题的猪的数量是动态的,要求在一个单位的试毒时间,找出唯一的一瓶毒药,最少用多少只猪。
那个题属于这个题的一个特殊情况,也就是当minutesToDieminutesToTest相等的时候,只有一个单位时间。

做法可以用给液体编号的方法,打开python命令行开始模拟计算math.log(1000)/math.log(2) 输出 9.965784284662087
也就是说,最少只要10只猪就能算出来1000个罐子里哪个有毒。

  • 第1桶液体的二进制编号为0000000001
  • 第2桶液体的二进制编号为0000000010
  • 第999桶液体的二进制编号为1111100111
  • 第1000桶液体的二进制编号为1111101000
    每个桶都编上了号码,现在让10只猪对应上二进制的10个bit位置,只要是1的,就喝。
    我们举个例子,假如第4,5,6只猪中毒身亡,如何计算是哪一桶液体有毒。
    第4,5,6只猪死亡,也就是代表第4,5,6个bit位置的数字是1,那么就是第111000,十进制的话就是56个桶,是有毒的,因为只有这个桶,恰好被第4,5,6只猪同时喝。

回到题目,给出了死亡时间,喝总的测试时间,那么就是说,我们可以把待测试的液体进行等分,分批次进行验证,只要有死亡的小猪,立刻得出答案,如果到了时间没有小猪死亡,那么换下一批。

也可以从信息角度思考,上链接,这是宫水三叶的题解
https://leetcode-cn.com/problems/poor-pigs/solution/gong-shui-san-xie-jin-zhi-cai-xiang-xian-69fl/
这块想搞清楚就稍微麻烦点了。

最后修改:2021 年 11 月 26 日
如果觉得我的文章对你有用,请随意赞赏