哪一瓶是毒药?
Time Limit:1000MS Memory Limit:65536K
Total Submit:360 Accepted:91
Description
记得宣讲会的时候，管大神讲过一道小白鼠测毒药的问题，现在我们来泛化一下这个问题。假设有N个瓶，由于瓶子上标签丢失，我们不知道瓶子到底是普通水还是毒药，但是唯一能确定的是，其中有且只有一瓶是毒药，其他都是普通水。由于毒药是慢性毒药，小白鼠喝下去可能要过几天才会死亡，为了节约时间，我们想一次性测出哪一瓶是毒药。但是由于实验室的小白鼠不是无限的，所以希望用尽量少的小白鼠来检测出毒药。亲爱的ACMer们，你有什么好的方案吗？
Input
有多组测试数据，每组测试数据输入一个整数N（0 < N < 10^8）
Output
输出最少使用的小白鼠数量。
Sample Input
1
2
Sample Output
01
一道非常非常好的题目啊啊啊啊啊啊！！！！！好到我直接五体投地；；
思想;是这样的，我们把n个瓶子（n个状态）标号为0~~n-1，假设1到n-1全部化成二进制最多k位，，那么我们把1~n中所有第k位为1的瓶子给第一个小白鼠喝，如果小白鼠死了，那么毫无疑问，有毒瓶子的第k位为1，如果没死，那么有毒瓶子第k位为0，接下来,第k-1位所有数字为1的瓶子给第2个小白鼠喝，如果小白鼠死了，那么该有毒瓶子的第k-1位为1，否则为0，后面以此类推，，不难得出总共需要的小白鼠的个数就是n-1的二进制位数
这个神算法 据说叫警官算法，一个侦探发现的，无比佩服
#include<stdio.h>
#include<string.h> int main() { int n; while(~scanf("%d",&n)) { int p=0; n--; while(n>=1) { p++; n>>=1;//因为是右移，所以n--1的最高位必定是1，而不会是0； } printf("%d ",p); } return 0; }