c*****e
发帖数: 3226 | 1 第一个鸡蛋第一次从第x层扔。如果碎了，则第二个鸡蛋在1～x-1层中一层一层往上线
性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔。
这里不明白，如果没碎， 为何不是第一个鸡蛋第二次从x+x层扔。 |
e********2
发帖数: 495 | 2 DP
【在 c*****e 的大作中提到】
: 第一个鸡蛋第一次从第x层扔。如果碎了，则第二个鸡蛋在1～x-1层中一层一层往上线
: 性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔。
: 这里不明白，如果没碎， 为何不是第一个鸡蛋第二次从x+x层扔。
|
n*******s
发帖数: 17267 | 3 扔个Bird, 第一层不碎的话， 第二层扔基本上都碎了。
回答你的问题， 原题是说有X个鸡蛋？
【在 c*****e 的大作中提到】
: 第一个鸡蛋第一次从第x层扔。如果碎了，则第二个鸡蛋在1～x-1层中一层一层往上线
: 性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔。
: 这里不明白，如果没碎， 为何不是第一个鸡蛋第二次从x+x层扔。
|
r*******e
发帖数: 340 | 4 时间复杂度的问题,
假设 共有N层楼梯， 鸡蛋在T层及以上会碎
你的方法类似binary search
需要lgN个鸡蛋， 平均复杂度是 lg(N)
原来的方法需要lgT个鸡蛋，平均复杂度是 sqrt(T) |
c*****e
发帖数: 3226 | 5 一堆人上来冒泡，没一个明白我问的问题？
【在 c*****e 的大作中提到】
: 第一个鸡蛋第一次从第x层扔。如果碎了，则第二个鸡蛋在1～x-1层中一层一层往上线
: 性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔。
: 这里不明白，如果没碎， 为何不是第一个鸡蛋第二次从x+x层扔。
|
c****g
发帖数: 3893 | 6 你问问题了?
【在 c*****e 的大作中提到】
: 一堆人上来冒泡，没一个明白我问的问题？
|
b**********5
发帖数: 7881 | 7 我也有同样的问题。 为什么不是x+(x-2)? or x+(x-3)? 这个减一是哪里来的？
【在 c*****e 的大作中提到】
: 第一个鸡蛋第一次从第x层扔。如果碎了，则第二个鸡蛋在1～x-1层中一层一层往上线
: 性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔。
: 这里不明白，如果没碎， 为何不是第一个鸡蛋第二次从x+x层扔。
|
n*******s
发帖数: 17267 | 8 因为你已经扔了一次了啊, 同学.
你问的是那个100层楼, 两个鸡蛋怎么扔的问题?
【在 c*****e 的大作中提到】
: 一堆人上来冒泡，没一个明白我问的问题？
|
c*****e
发帖数: 3226 | 9 总算有人和我一样的困惑了。 不容易，一堆南郭先生。。。
【在 b**********5 的大作中提到】
: 我也有同样的问题。 为什么不是x+(x-2)? or x+(x-3)? 这个减一是哪里来的？
|
n******n
发帖数: 12088 | 10 保证最坏情况下最优。
【在 c*****e 的大作中提到】
: 总算有人和我一样的困惑了。 不容易，一堆南郭先生。。。
|
c******z
发帖数: 38 | |
l******s
发帖数: 3045 | 12 应该是始终从总层的开方层上扔吧。以100层总数为例，第一次是10层，如果不破第二
次总层为90,开方取整为9.
【在 c*****e 的大作中提到】
: 第一个鸡蛋第一次从第x层扔。如果碎了，则第二个鸡蛋在1～x-1层中一层一层往上线
: 性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔。
: 这里不明白，如果没碎， 为何不是第一个鸡蛋第二次从x+x层扔。
|
x**********g
发帖数: 44 | 13 这里x表示最优解，用两个鸡蛋最多drop x次能得到答案
第一次扔了鸡蛋没碎，已经用掉了一次drop，只剩x-1次drop的机会了呀。
如果从x+x层扔，碎了，这时候你用掉了两次机会，你无法用drop-2次在 x-1层找出答案
【在 c*****e 的大作中提到】
: 第一个鸡蛋第一次从第x层扔。如果碎了，则第二个鸡蛋在1～x-1层中一层一层往上线
: 性搜索，最多x-1次；如果没碎，则第一个鸡蛋第二次从x+(x-1)层扔。
: 这里不明白，如果没碎， 为何不是第一个鸡蛋第二次从x+x层扔。
|
w****r
发帖数: 15252 | |
