可怜的小猪

有1000只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在15分钟内死去。

问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？

回答这个问题，并为下列的进阶问题编写一个通用算法。

进阶:

假设有 n 只水桶，猪饮水中毒后会在 m 分钟内死亡，你需要多少猪（x）就能在 p 分钟内找出"有毒"水桶？n只水桶里有且仅有一只有毒的桶。

可怜的小猪，被拿去做实验了。

先看1只小猪，60分钟的话，它最多可以判断出 60/15+1 = 5只水桶中的毒药桶。每隔十五分钟喝一次水，喝四次，如果幸运的话活了下来，就是最后一桶。

再接着看2只小猪，60分钟，它最后可以判断出25只水桶，可以这样：

00 01 02 03 04

10 11 12 13 14

20 21 22 23 24

30 31 32 33 34

40 41 42 43 44

将桶像上面摆放，第一只猪喝掉第一位为0的混合后的水，每隔15分钟喝一次，这样如果不幸运，在x行被毒死了，则证明毒药在第x行；在第一只猪猪和的同时让第二只猪猪喝掉第二位为0的混合水，如果在y列被毒死，则毒药在第y列。这样第一只猪猪判断出了横坐标x，第二只猪猪判断出来纵坐标y，则可以知道哪桶水有毒。

 1 class Solution {
 2     public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
 3 
 4         if(buckets == 1) return 0;
 5 
 6         int w = minutesToTest / minutesToDie + 1;
 7         int re = 1;
 8         while(Math.pow(w,re) < buckets)
 9             re ++;
10 
11         return re;
12     }
13 }

Leetcode 458.可怜的小猪

原文：https://www.cnblogs.com/kexinxin/p/10280216.html