本文主要是介绍LeetCode-Poor_Pigs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
Answer this question, and write an algorithm for the follow-up general case.
Follow-up:
If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the "poison" bucket within p minutes? There is exact one bucket with poison.
翻译：
那里有1000个桶，其中只有一个装的是毒药，剩余的装的是水。他们看起来都是一样的。如果一直猪喝了毒药，它将在15分钟内死去。你需要在一个小时的时间内用最少数量的猪找到装了毒药的桶。
回答这个问题，对于下述引申的例子写下一个算法。
思路：
(摘自https://blog.csdn.net/wilschan0201/article/details/72519147，说的很清楚明白，就不自己总结了。)
1. 一只猪在一小时内最多能验多少桶？
一次喝一个桶的，15分钟后没挂再喝第二桶，一小时60分钟内可以喝 60/15 = 4 次，如果有5桶水，那个只要喝前4桶就只能第5桶是否有毒。
因此一只小猪在一小时可以验5桶水
2. 两只呢？
既然一只能验5桶，那么用二维的思路，2只猪应该可以验5*5桶：
猪A负责行，猪B负责列，每15分钟试喝一行/一列的所有5桶水，通过2只猪上天的时间能推断出毒水在几行几列。
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
3. N只
如此类推到N只的情况，使用N维去分区，则5^N >= 1000即为解决本题的公式。
C++代码（Visual Studio 2017):
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;class Solution {
public:int poorPigs(int buckets, int minutesToDie, int minutesToTest) {if (buckets <= 1)return 0;int k = minutesToTest / minutesToDie + 1;int x = 1;while (x < buckets) {if (pow(k, x) >= buckets)return x;x++;}}
};int main()
{Solution s;int buckets = 1000;int minutesToDie = 15;int minutesToTest = 60;int result;result = s.poorPigs(buckets, minutesToDie, minutesToTest);cout << result;return 0;
}这篇关于LeetCode-Poor_Pigs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
