1、要保证鸡蛋的硬度能被正确测量出来,则当只有一个鸡蛋是,只能从第一楼开始一层一层的测。
2、当有两个鸡蛋时,则用二分法原则先测一下第50层,若鸡蛋破了,则只剩下一个鸡蛋,又要从第一楼开始慢慢测。
若鸡蛋在第50层没破,则再测一下第75层,若破了,则用另一个鸡蛋从第51层开始慢慢的测。
若鸡蛋在75层没破,则继续下去......
3、当有三个鸡蛋时......
nothing is impossible
1、要保证鸡蛋的硬度能被正确测量出来,则当只有一个鸡蛋是,只能从第一楼开始一层一层的测。
2、当有两个鸡蛋时,则用二分法原则先测一下第50层,若鸡蛋破了,则只剩下一个鸡蛋,又要从第一楼开始慢慢测。
若鸡蛋在第50层没破,则再测一下第75层,若破了,则用另一个鸡蛋从第51层开始慢慢的测。
若鸡蛋在75层没破,则继续下去......
3、当有三个鸡蛋时......
按照这个说法,对于第一个例子:100,2
最坏情况就是 先用2分法测第一层,然后鸡蛋破了。所以第二个只能从第一层开始,那最坏情况就是49 了?
答案怎么是14,哪个高手解释一下
/* f[0][h]=INF ;f[0][0]=0; f[n][h]=min{ max{f[n-1][h1-1],f[n][h-h1]}+1 ,h1=1,2,...,h } */ #include <stdio.h> #define INF 1000000 #define max(x,y) ((x)>(y)?(x):(y)) int _f[2][100001]; struct { int* operator [] (int i){ return _f[i&1]; } }f; int main() { int N,H; while(scanf("%d%d",&N,&H)!=EOF){ int res=-1; for(int h=0;h<=H;h++){ f[0][h]=INF; } f[0][0]=0; for(int n=1;n<=N;n++){ f[n][0]=0; for(int h=1;h<=H;h++){ f[n][h]=INF; for(int h1=1;h1<=h;h1++){ f[n][h]<?=max(f[n-1][h1-1],f[n][h-h1])+1; } } if(n>=f[n][H]){ res=f[n][H]; break; } } printf("%d\n",(res!=-1?res:f[N][H])); } }