458.poorpigs
题目：458. poor-pigs （可怜的小猪）
原题地址： https://leetcode.com/problems/poor-pigs/
有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。
问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？
回答这个问题，并为下列的进阶问题编写一个通用算法。
进阶:
假设有 n 只水桶，猪饮水中毒后会在 m 分钟内死亡，你需要多少猪（x）就能在 p 分钟内找出 “有毒” 水桶？这 n 只水桶里有且仅有一只有毒的桶。
提示：
- 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
- 小猪喝完水后，必须有 m 分钟的冷却时间。在这段时间里，只允许观察，而不允许继续饮水。
- 任何给定的桶都可以无限次采样（无限数量的猪）。
解题思路
读完题目之后，第一直觉想到的就是这是一道考进制数题目，因为一上来就提到1000这样的数字，而最后问的是需要多少只猪，凡是“需要多少x才能做到y”，而y又是跟一个数字变量有关的，这样的题目一般来说就是考进制数。现在来说还为时过早，那我们就暂且先有这样的一个猜测，继续探索。仔细分析这个问题我们可以发现这里面有几个变量，我们先把变量找出来，一共4个：1) 水桶的个数n；2）猪的个数x；3）总时间p；4）猪饮水后知道结果的时间m。
变量有4个，数目有点多，因此要分析题目的这个问题，先固定其中的一些变量不变，变动其它的变量，通过这种方式来探索看看会不会有什么新发现。先让m<p<2m，这个时候小猪们只够时间喝一次水，问有n个水桶需要多少只猪，这个问题不好回答，还是要再分解探索。正面不好得到答案，我们反过来想，假设有x只猪的情况，最多可以从多少个水桶中找出有毒的那个？（下面把问题简化为x只猪能测试多少个桶？）
发现这个问题我们还是不能一下子回答出来。不慌，那就继续先从简单的开始想。1只猪能测试多少个桶呢？
图1 一只猪可以测试2个桶
很明显1只猪最多只能测试2个桶。那2只猪呢？
图2 两只猪可以测试4个桶
2只猪可以测试4个桶。到了这一步，我们开始有点感觉了，一开始直觉告诉我们它很有可能是一个跟进制数有关的问题，如果是于进制数有关的话，那必然跟两个变量有关，一个是位数，另一个是看它是多少进制，即x位的s进制数最多可以表示s^x个数，比如3位二进制数可以表示2^3=8个数。此时马上就意识到以下这两个问题很像：1）x位的s进制数最多可以表示多少个数（答案我们都知道，是s^x）？2）x只猪能测试多少个桶？观察上图，很容易让人联系到二进制编码。再加上，刚才的结论1只猪的时候可以测试2个桶，2只猪可以测试4个桶，让我们联想到，如果这真的是进制数的问题的话，猪的个数可能是x，而底数是2，即2^x。先别急，先回到上面那幅图，如果是二进制编码，那这4只桶就应该可以编号为00、01、10、11，那0和1有对应着什么呢？这关系比较难理解，于是我们再回头看第一幅图，也就是只有一只猪的情况，这时候就有头绪了，两只桶应该编号为0、1，那显然猪的数量就是位数x，0和1表示的是猪有没有被毒死，0表示猪没有被毒死，1表示猪被毒死了。那00就表示两只猪都没有被毒死，01就表示其中一只猪A被毒死，另一只猪B没被毒死，10就是A没死B死了，11表示两只猪都死了。
图3 图2所对应的编码方式
将编码的和图2结合起来，可以发现1的地方就有连线。那我们看下3只猪的情况下，是不是真的可以测试2^3=8个水桶呢？
图4 3只猪的情况
通过画出图3，我们发现3只猪的确是可以测试8个水桶。所以，有多少只猪就表示有多少位，而且第i位上面的数字对应着第i只猪的状态（没被毒死为0，被毒死为1），那怎么理解这个连线呢？如果某一桶水有毒，那喝了这桶水的猪就必定会被毒死，假设这桶水的编码是101，它代表的意思明显是说如果要测试出这桶水是有毒的话，理论上最终状态应该是第一只猪和第三只猪都被毒死，而第二只猪没有被毒死。一桶毒水怎么才能只毒死两只猪而另外一只猪没死呢？那就只能是另外那只猪没喝这桶水，所以101这个圆圈就肯定会被连上两条线，一条连着第一个三角形（第一个三角形代表第一只猪），另外一条连着第三个三角形（第三个三角形代表第三只猪）。
基于上面的探索，我们可以进一步用一个向量V来表示“一个水桶如果被测试出是有毒的话，它的理论状态”，（v1, v2, v3），v1,v2,v3∈ {0, 1}，例如101实际上可以写成向量（1, 0, 1）。因此有，向量空间中的每个点都对应着一桶水，而这个点的坐标表示如果这桶水有毒时，那些猪应该处于何种状态，例如(0,0,0)表示如果三只猪都没有被毒死就能验证出这个桶的水有毒；(0,0,1)则表示如果第三只猪被毒死而其余两只猪没事，就能验证出这个桶的水有毒。
那么问题来了，我们虽然建立了一个“水桶编号和猪的状态之间的对应关系"，但这些猪要怎么喝水才能表现出这些状态呢？（第一只猪喝哪几个桶的水？第二只猪喝哪几个桶的水？.....）根据之前的分析，向量(v1, v2,...,vi,...vx)里面vi这只猪应该喝编号中vi=1的水桶。以x=2为例，我们可以画出以下的表格，猪#1按列喝水，猪#2按行喝水，最后一列和最后一行不喝。
我们发现其实猪喝哪些水桶的水可以不固定，只要所有猪的最终状态能唯一确定表格中的一个格子（向量空间中的一个点）就可以了。比如我们也可以变成：
那三只猪的情况怎么办呢？三只猪的时候(v1, v2, v3)是一个三维向量，所以向量空间是一个三维空间，画出来会是一个二阶魔方，每个格子都对应着一个水桶。
v1,v2,v3这三只猪分别喝编号在不同平面的，我这里把它们应该喝的水桶，分别用了三种不同颜色标了出来。
以上是 458.poorpigs 的全部内容， 来源链接： utcz.com/z/517490.html
