基本算法连载（2）－摔xbox

• 题目

You have been given 2 special, extremely rugged Xboxes. You are in an office building that is 100 stories high. Using the fewest possible number of drops from windows in your office building, determine the highest floor you can drop an Xbox from and have it survive: for example, they might be able to take the drop from the 30th floor, but not the 31st. You can break both Xboxes in your search. State the worst case number of drops needed and explain how you arrived at that answer.
你在一幢100层的办公楼里上班，现在给你两台xbox（已经特意捆绑包扎好），要求你用尽可能少的试摔次数来判断xbox摔不坏的最高楼层层数。比方说，从30层丢下来没问题，但从31层丢下来就不保了。在摸索过程中，允许把两台xbox都砸烂。在最坏情况下，使得试摔次数尽可能小。

• 分析

1. 问题答案必须是在最坏情况下，时间复杂度最小。
2. 最容易想到的就是二分法，三分法，多分法，但它们并不符合要求。比如：在50层丢一个，被砸烂。然后在25层丢另外一个，同样被砸烂。此时根本无从找到问题答案。
3. 第二个想到的方法就是分段。（1）用第一个xbox寻找损坏区间；（2）用第二个xbox遍历该区间寻找损坏层。假定最优区间长度是x，则第一步最多要摔100/x（大于等于此值的最小整数）次，第二步最多摔x-1次，问题转换为求100/x+(x-1)的最小值。具体描述：以10层楼为一个区间，先摔第一个，以确定摔坏的区间，然后再用另一个在这个区间内从最低的楼层摔，从而找到所要求层数，这种方法最多要摔19次。
4. 在“分段”方法中，段区间都是相等的。如果段区间不等，是不是可以找到最优的方法呢？假设最终答案至少要摔n次，那第一次顶多从n层楼摔。如果坏了，第二 个从1至n-1层最多摔n-1次就可以判断了；如果没坏，那么搜索范围改为[n+1,100]，相当于搜索空间减少了n层。如果第一次没坏，第二次顶多再 减少n-1的搜索空间。依次类推，当第n次时顶多再减少1的搜索空间。n次之后，顶多排除n+(n-1)+(n-2)+...+1 = n*(n+1)/2个楼层。只要n*(n+1)/2 >= 100就可以了，满足这个条件的最小n为14。具体描述：从14楼丢一个，如果碎了，从1楼开始到13楼为止丢另一个，不碎，在14＋13楼丢；...

• 证明

给一个包含n个元素的数组，{a[1],...,a[n]}，a[1]+a[2]+...+a[n]=100。那么如果第k次摔坏了第1台xbox ，那么此时最坏情况下总共需要的次数是k+a[k]-1我们把这个记为cost[k]。此时，问题可以重新描述为：找到一个满足上述条件的数组，{a[1],...,a[n]} ，使得 max(cost[k])最小。
sigma( cost[k] )
= (1+a[1]-1) + (2+a[2]-1) + (3+a[3]-1) ... + (n+a[n]-1)
= (1+2+3+ ... +n) + (a[1]+a[2]＋a[3]+ ... +a[n]) - n
= n*(n+1)/2 + 100 - n
这个式子是个常量仅与n有关，与{a[1],...,a[n]}的具体数值无关。同时，不难看出 max( cost[k] ) >= sigma( cost[k] ) / n （最大值总是大于平均值），而且仅当 cost[1] =cost[2] = ... cost[n] 的时候，max...可以取到这个最小值。因此，对于任意给定的n，满足 cost[1]= cost[2] = ... cost[n]的解就是最优解。也就是说k+a[k]-1=1+a[1]-1，从而a[k]=a[1]-k+1 。那么a[2]=a[1]-1，a[3]=a[1]-2=a[2]-1...

参考：(1) 摔xbox的题目