【机试】2015年腾讯后台开发暑期实习生校招一面

题目大意

有一栋100层高的大楼，给你两个完全相同的玻璃球，假设从某一层开始丢下玻璃球会摔碎，怎么利用手中的两个玻璃球，用什么最优策略（最少次数）知道这个临界的层是第几层

解题思路

动态规划。 这个题目首先是关于“最优”的定义，考虑best-worse case最坏情况下最优。 记n层楼2球的问题为Q(n,2),对应的最坏情况最优解为ba(n,2); 对于从第k层处抛球，对应的有如下两种情况：

球破了。临界值肯定落在第k-1层到第1层之间，而现在手中就只剩下一个球了，此时的问题变为ba(k - 1, 1)。显然，为了找到临界值，唯一的做法就是从最底层逐步向上找，最坏情况为k-1次。即ba(k - 1, 1) = k-1。球没有破。临界值肯定落在第k+1层到第n层之间，球没有破还可以再次利用。所以，此时问题就变为了n-k层楼的2球问题。即ba(n - k, 2)。

由于要考虑的是最坏的情况，所以上述两种情况应该取次数多的那一个。而为了找到最优解，就应该遍历k，找到值最小的那一个。所以，综合起来，为了找到最坏情况最优解，则有如下状态转移方程。

ba(n, 2) = min{1 + max{k - 1, ba(n-k,2)}} for k = 1 to n

实现细节：

由于只是2球问题，1球情况的最坏值是确定的，所以可以直接使用一个一维数组dp来表示ba(n,2)由于k>0, 所以 n-k < n，也就是说，每个情况都依赖与之前的情况，所以让n从1开始增长，就可以确保后续运算过程中，早前的情况都已经计算过了

CPP代码

#include <iostream> #include <algorithm> #include <climits> using namespace std; class Solution { public: int throwBall(int n) { int *dp = new int[n]; dp[0] = 1; //测试一个i层的楼的临界值 for (int i = 1; i < n; ++i) { int curMin = INT_MAX; //从第k层处抛球 for (int k = 1; k <= i; ++k) { // i - k < i，而由于i是增长的，所以此处dp[i-k]一定计算过了 //取两者中最坏情况 int temp = max(k, 1 + dp[i - k]); if (temp < curMin) curMin = temp; } //记录最优抛球次数 dp[i] = curMin; } //由于初始为0，所以n层在这里应该返回n-1 int ans = dp[n - 1]; if (dp != NULL) { delete dp; dp = NULL; } return ans; } }; int main(int argc, char const *argv[]) { int n = 100; Solution a; cout << a.throwBall(n) << endl; return 0; }