题意:有n瓶药剂,其中只有一瓶药剂有毒。让你用最少的小白鼠试出哪瓶有毒。你只有一次给任意只小白鼠各喂食任意种类药剂的机会。
m只老鼠就能对应2^m种“生死状态”的组合,给每种状态分配一个种类的药剂,然后给每只老鼠喂食“如果它在这种药剂对应的生死状态下死去”的所有药剂,就可以根据发生的死亡情况,分辨出哪瓶药剂有毒。
比如老鼠数有3只。
000 1
001 2
010 3
100 4
110 5
011 6
101 7
111 8
给一号鼠喂4578
给二号鼠3568
给三号鼠2678。
所以答案为(ceil)log2(n)。
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int T,n;
int main(){
scanf("%d",&T);
for(;T;--T){
scanf("%d",&n);
if(n==1){
puts("0");
continue;
}
for(int i=1;i<=30;++i){
if((1<<i)>=n){
printf("%d\n",i);
break;
}
}
}
return 0;
}