[LeetCode]Poor Pigs

这道题我们要用最少的猪在限制的时间找出毒药。有1000个桶，60分钟限时，15分钟发作。我们先从最基本的方法开始想，如果我们用250头猪，每个猪尝四次，那么60分钟内肯定是可以找出毒药的。但是如果每一头猪可以尝多个桶的话，我们就可以根据15分钟后的状态缩小范围。比如，如果我们用编号为1-9的九头猪，每个猪尝100个桶，那么15分钟之后，我们就能确定毒药是在哪100个桶当中，如果编号为i的猪死了，就在它尝过的100个桶中；如果没有猪死，那么就在剩下的100个桶当中。以此类推，我们一步一步缩小范围。那么对于1000个桶，我们可以用7头猪：

1. 0分钟: 每个猪尝125个桶
2. 15分钟: 最坏情况死了一头猪，还剩6头。范围缩小到125个桶，每头尝17/18个桶
3. 30分钟: 最坏情况还剩5头，和18个桶。每头猪尝3个桶。
4. 45分钟: 最坏情况还剩4头猪，和3个桶。分配两头猪尝，每个尝一桶。
5. 60分钟: 我们找到藏毒的桶。

具体实现的时候我们用二分即可。但是很可惜这并不是正确答案，最后看别人的解答，还有更好的方法。假设我们有25个桶，60分钟限时，15分钟发作。我们把桶排列成一个二位矩阵：

• 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

我们用两头猪即可解决问题。一头猪每次尝一行，那么60分钟可以尝四行，并且确定有毒的在哪一行(如果猪没死就在没尝的那一行)。列同理，所以我们在60分钟内确定了有毒的桶在矩阵当中的坐标。如果桶更多，我们就加维度，依次类推：

• 三头猪可以处理<= 125个桶
• 四头猪可以处理<= 625个桶
• 五头猪可以处理<= 3215个桶

这个比我们之前的方法效率更多。所以1000个桶我们只需要五头猪。至于为什么这一定是最小的数量，并不会证明。

所以我们只要根据这个思路把代码写出来即可，代码本身是很简单的。假设有n个桶，限时m分钟，毒p分钟发作。时间复杂度为O(logm/p(n))，代码入选：

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

view raw Poor Pigs.cpp hosted with ❤ by GitHub