[数据结构与算法]LeetCode - 每日一题 458.可怜的小猪

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int pigs = 0;
        double time = minutesToTest/minutesToDie+1;
        while(buckets > Math.pow(time,pigs)){
            pigs++;
        }
        return pigs;
    }
}

题目解析：

????????一共有buckets个桶，其中一个桶里有毒药， 小猪喝了后minutesToDie分钟后就死了，现在有minutesToTest分钟，问：至少需要几个猪就可以在给定时间内测出哪一个桶有毒药。

答案解析：

????????如果有1000桶水， 15min后毒发， 60min内需要几个猪可以找到毒桶。

????????如果是一只猪， 可以在60min内喝四个桶的水，如果都没事，那么第五个桶肯定是毒桶。可以得出一只猪，可以测出五个桶。

????????如果是俩只猪， 那么可以喝5 *5 = 25桶水。 其中一只猪从左往右喝五桶，一只猪从上往下喝五桶，那么可以在四次后确定出唯一的一桶毒桶。

? ? ? ? 所以，答案其实就是 (minutesToTest/minutesToDie+1)^pigs > buckets 就可以得出最小猪的数量。

????????????????