题目描述

总共有1000个罐子,其中有且只有1个是毒药,另外其他的都是水. 现在用一群可怜的猪去找到那个毒药罐. 已知毒药让猪毒发的时间是15分钟, 那么在60分钟之内,最少需要几头猪来找出那个毒药罐?

写一个程序，给定罐子数目，给定测试时间和死亡时间，求出最少需要的猪的数目。

样例

无

算法

(数学) $O(log(n))$

先考虑二维的情况，假如有25个罐子
我们将罐子排列如下：
1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25
分两只猪。
第一只去寻找列坐标，第二只去寻找行坐标。
以第一只为例，先在0分钟喝下1,6,11,16,21桶水， 再在15分钟喝下 2 7 12 17 22桶水。 再在第30分钟喝下3 8 13 18 23桶水 再在 45分钟喝下 4 9 14 19 24 29桶水 这时候如果没有死， 那么毒水在第5列。如果在其中某一时间段死了，那么也可以确定相应的列。

那么同理，利用第二只猪可以确定行数。
那么同理，如果有三只猪，就可以确定三维的情况了。

故 (n^res) >= buckets。
n即为测试时间除以中毒检验时间再加一（之前说过可以通过排除法确定最后一列）。

时间复杂度分析：依次增加猪的数目，计算次方，判断是否足够,由于是次方运算，所以复杂度为 $O(log(buckets))$。

C++ 代码

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int pigs = 0;
        while(pow((minutesToTest/minutesToDie)+1,pigs)< buckets)
            pigs++;
        return pigs;
    }
};