腾讯面试题，整理一下答案。

两颗玻璃球测临界高度问题

问题描述

台阶的高度差序列可以用一个数组来描述

$$h_{1},h_{2},\cdots,h_{i},\cdots,h_{N},$$

$N$表示台阶总的数量，且$h_{i}<h_{i+1}$。设玻璃球能够承受的高度差为$x$。玻璃球在某一个台阶实验一次就等价于$x$与对应的$h_{i}$比较了一次大小。如果$x<h_{i}$，则玻璃球就会破裂。假设总共有两个一模一样的玻璃球，请设计最优策略找到临界台阶（假设一定存在临界台阶）。

最优策略

以$N=100$为例，则最优策略分为两步：

• 让$x$同以下序列依次比较，直到第一颗玻璃球破裂：

  $$h_{a}^{1},h_{a+(a-1)}^{2},\cdots,h_{\sum_{i=1}^{j}(a-i+1)}^{j},\cdots,h^{K}_{\sum_{i=1}^{K}(a-i+1)},$$

  其中，$a=14$。且$K=11,\sum_{i=1}^{K}(a-i+1)=99$。添加最后一项后，上述序列直观表示为:

  $$h_{14},h_{27},\cdots,h_{95},h_{99},h_{100}.$$

  若玻璃球在$h_{100}$处破裂，那么临界台阶就是最后一个台阶；否则转步骤二。(称之为试错阶段)

• 不妨设第一颗玻璃球在$h_{\sum_{i=1}^{j}(a-i+1)}^{j}$处破裂。那么就利用第二颗玻璃球从$h_{1+\sum_{i=1}^{j-1}(a-i+1)}^{j-1}$ 处开始，按照原始台阶的顺序依次向后试验，直到找到临界台阶。(称之为线性扫描阶段)

最优性证明

必须承认，对于一般的$N$，我还没有找到确定$a$的确切办法。但是在$N=100$的情况下，能够明确证明上述$a=14$的两阶段策略，是最坏情况下比较次数最小的最优策略。证明分为3步。第一步证明最优策略一定是上述两阶段策略的形式，特别是第二阶段一定为线性扫描阶段；第二步找到一个次优解，用以帮助第三步证明中排除掉一些明显不可能的策略，使得剩下可能的策略为有限多个；第三步通过枚举法证明$a=14$是最优的策略。

Step 1

所有的策略都可以抽象为两个序列。具体而言，第一个序列是第一颗玻璃球同台阶的比较序列，第二个序列是第二颗玻璃球同台阶的比较序列。Step 1断言第二颗玻璃球的比较序列一定是连续的台阶。若不然，那就意味着第二颗玻璃球的比较序列中存在跳跃比较的情况。基于此，总可以构造这样的最坏情况，使得被跳跃过的台阶为临界台阶。此时因为第二颗玻璃球在临界台阶之后的台阶上试验过，从而破碎掉，导致算法再也没有办法真正找到临界台阶，从而可以认为实验次数为无穷大。这显然不可能是最优策略。所以最优策略的第二个比较序列一定是线性扫描的形式。

Step 2

基于Step 1的结论，我们只需要讨论策略的第一个比较序列即可。我们假设第一个比较序列为：

$$h_{n_{1}},h_{n_{2}},\cdots,h_{n_{i-1}},h_{n_{i}}\cdots,h_{n_{K-1}}.$$

上述序列是原始台阶高度差序列的一个子序列。我们定义$h_{n_{i}}$和$h_{n_{i-1}}$之间差了$\Delta n_{i}$个台阶，显然

$$\Delta n_{i}=n_{i}-n_{i-1},2\leq i \leq K-1$$

那么我们就会有如下的关于$\Delta n_{i}$的序列（规定$\Delta n_{1}=n_{1}-1,\Delta n_{K}=100-n_{K-1},$）

$$\Delta n_{1},\Delta n_{2},\cdots,\Delta n_{i},\cdots,\Delta n_{K}.$$

构造上述序列的动机是为了方便讨论待证明的策略的最坏情况比较次数。显然，当应用上述两阶段形式的策略时，线性扫描阶段的试验次数只会是$\{\Delta n_{i}\}$中的某一个（假设就是在$h_{n_{j+1}}$个台阶处，第一颗玻璃球碎掉）。而试错阶段也会有若干次的试验，显然试验次数是$j+1$。那么最坏情况下，试验次数一定满足不等式（可能取得的最大的扫描次数加上可能取得的最大的试错次数）:

$$worst \leq \max\limits_{i=1,\cdots,K}\{\Delta n_{i}\}+K$$

一种较为简单的思路是，如果约束$\Delta n_{i}$的最大值尽可能的小，那么$worst$就可能很小。根据鸽舍原理，把$N$个物品分为$K$份，其中一定有一份比$\frac{N}{K}$来得多。所以$\max\limits_{i=1,\cdots,K}\{\Delta n_{i}\}$的最小值就是$\frac{N}{K}$，且此时每一份$\Delta n_{i}$都是$\frac{N}{K}$：这就是说这对应着一个等分的策略。那么显然此时的最坏情况是第一颗玻璃球一直实验到了最后才破碎，然后第二颗玻璃球对最后一份$\Delta n_{K}$做了线性扫描。此时

$$worst = \frac{N}{K} + K$$

稍加分析，当$K=\sqrt{N}$时，$worst$取得最小的$2\sqrt{N}$。具体将$N=100$带入，那么我们将台阶序列10等分，并且第一颗玻璃球按照以下序列依次与台阶比较

$$h_{10},h_{20},h_{30},\cdots,h_{90},h_{100}.$$

那么最坏情况下，策略需要比较上述序列的10次，再加上$h_{91}$到$h_{99}$的9次试验。共计19次实验。

Step 3

上述做法的一个问题是，我们只针对可能取得的最大的扫描次数做了优化，并没有对扫描次数加上试错次数整体做优化。所以改进的思路应当是保证最坏情况下，扫描次数加上试错次数依然比19次来得小。同时Step 2的结果也表明，那些$n_{1}\geq19$的策略都不可能是最优策略。因为有可能它们的第一颗玻璃球在$h_{n_{1}}$处就破裂了，而后线性扫描阶段的次数显然会超过19次，因而不会是最佳策略。

进一步可以归纳，只有那些符合下述模式的策略才可能成为最佳策略：

$$\begin{equation} \Delta n_{i}=\Delta n_{i-1}-1 \end{equation}$$

这是因为当$\Delta n_{i}\geq\Delta n_{i-1}$时，该策略的最坏情况会在最后一次试错的时候发生，且此时累计的试错次数加上线性扫描次数会远远大于$\Delta n_{1}$。而我们可以证明当上述模式被满足时，该策略的最坏情况试验次数就等于$\Delta n_{1}$。当$\Delta n_{i}<\Delta n_{i-1}-1$时，该策略会留下更多的尾项，使得对应的最坏情况下试验次数有可能变大。所以它们不会比符合$\Delta n_{i}=\Delta n_{i-1}-1$的策略来得更好。

而当$\Delta n_{i}=\Delta n_{i-1}-1$时，无论第一颗玻璃球碎在哪颗$h_{n_{i}}$上，此时线性扫描次数加上试错次数都会等于$\Delta n_{1}$ 。这一点可以通过数学归纳法证明，不再赘述。

通过上述讨论，我们可以确定还没有排除的策略是有限多个的。这些策略符合两个限制条件：

• $\Delta n_{1}\leq 18$
• $\Delta n_{i}=\Delta n_{i-1}-1$

所以利用枚举法，理论上可以穷举18种情况，完成证明。对于$N=100$而言，当$a=14$为最佳策略。

总结

上述证明，虽然不能给出一般$N$情况下，最佳策略的解析解。但是它启发我们可以利用$2\sqrt{N}$作为一个界限，将数量巨大的可能的策略数目缩减为有限多个，而后利用暴力搜索，找到最佳策略。