[蓝桥杯]耐摔指数

耐摔指数

题目描述

X 星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。

各大厂商也就纷纷推出各种耐摔型手机。X 星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

X 星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的 2 楼。

如果手机从第 7 层扔下去没摔坏，但第 8 层摔坏了，则手机耐摔指数 = 7。

特别地，如果手机从第 1 层扔下去就坏了，则耐摔指数 = 0。

如果到了塔的最高层第 nn 层扔没摔坏，则耐摔指数 = nn。

为了减少测试次数，从每个厂家抽样 3 部手机参加测试。

如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

输入描述

一个整数 n（3<n<10000n（3<n<10000）,表示测试塔的高度。

输出描述

输出一个整数，表示最多测试多少次。

输入输出样例

示例

输入

3

输出

2

样例解释

手机 aa 从 2 楼扔下去，坏了，就把 bb 手机从 1 楼扔；否则 aa 手机继续 3 层扔下。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 2107  |  总提交次数: 2942  |  通过率: 71.6%

难度: 困难   标签: 2018, 省赛, 递推

算法思路

这个问题是经典的动态规划问题，核心是求解在 3 部手机、n 层楼的情况下，采用最佳策略在最坏运气下确定手机耐摔指数所需的最大测试次数。

关键思想：

1. ​​动态规划状态定义​​：

   • dp[i][j] 表示有 i 部手机和 j 层楼时，确定耐摔指数所需的最多测试次数
   • i 表示手机数量（1-3），j 表示楼层高度

2. ​​状态转移方程​​：

   • 当在第 k 层扔手机时：
     • 如果摔坏：则问题变为 i-1 部手机测试 k-1 层楼
     • 如果没坏：则问题变为 i 部手机测试 j-k 层楼
     • 最坏情况取两者最大值：max(dp[i-1][k-1], dp[i][j-k]) + 1
   • 最佳策略取所有 k 的最小值：

     dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], dp[i][j-k]) + 1)

3. ​​边界条件​​：

   • 只有 1 部手机时：dp[1][j] = j（必须逐层测试）
   • 0 层楼时：dp[i][0] = 0（无需测试）

算法过程演示

C++ 代码实现

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;const int MAX_N = 10005;int main() {int n;cin >> n;// dp[i][j]: i部手机测试j层楼的最大测试次数int dp[4][MAX_N] = {0};// 初始化：只有一部手机时for (int j = 1; j <= n; j++) {dp[1][j] = j;}// 两部手机的情况for (int j = 1; j <= n; j++) {dp[2][j] = INT_MAX;for (int k = 1; k <= j; k++) {// 摔坏：测试k-1层，剩1部手机；没坏：测试j-k层，剩2部手机int cost = max(dp[1][k-1], dp[2][j-k]) + 1;dp[2][j] = min(dp[2][j], cost);}}// 三部手机的情况for (int j = 1; j <= n; j++) {dp[3][j] = INT_MAX;for (int k = 1; k <= j; k++) {// 摔坏：测试k-1层，剩2部手机；没坏：测试j-k层，剩3部手机int cost = max(dp[2][k-1], dp[3][j-k]) + 1;dp[3][j] = min(dp[3][j], cost);}}cout << dp[3][n] << endl;return 0;
}

代码解析

1. ​​初始化​​：

   • dp[1][j] = j：只有一部手机时，必须逐层测试
   • dp[i][0] = 0：0层楼无需测试

2. ​​状态转移​​：

   • 对于每个楼层数 j，尝试所有可能的测试楼层 k（1 到 j）
   • 计算最坏情况下的测试次数：max(摔坏情况, 未坏情况) + 1
   • 取所有 k 中的最小值作为最佳策略

3. ​​复杂度​​：

   • 时间复杂度：O(n²)，对于 n 层楼，内部循环 n 次
   • 空间复杂度：O(n)，只需存储当前和前一状态

实例验证

输入	输出	验证过程
3	2	手机a从2楼测试：<br> - 若坏：手机b从1楼测试<br> - 未坏：手机a从3楼测试
7	3	手机a从4楼测试：<br> - 若坏：用2部手机测试1-3层（需2次）<br> - 未坏：用3部手机测试5-7层（需2次）
1000	19	符合蓝桥杯官方答案

注意事项

1. ​​边界处理​​：

   • 当 k=1 时：dp[i-1][0] = 0
   • 当 k=j 时：dp[i][0] = 0

2. ​​最坏情况保证​​：

   • 必须取 max(摔坏情况, 未坏情况) 保证最坏运气
   • 必须取 min 保证最佳策略

3. ​​数值范围​​：

   • 使用 INT_MAX 初始化确保正确取最小值
   • n < 10000 时不会溢出

测试点设计

测试类型	输入范围	验证重点
边界值	n=3	最小有效输入
特殊值	n=7	样例验证
性能测试	n=9999	最大边界值
功能测试	n=100	中等规模验证
错误输入	n=2	输入范围检查

优化建议

1. ​​双指针优化​​：

   // 在三部手机循环中添加
   int k_opt = 1;
   for (int j = 1; j <= n; j++) {// 利用单调性寻找最优kwhile (k_opt < j && dp[2][k_opt] < dp[3][j - k_opt - 1]) {k_opt++;}dp[3][j] = min(dp[3][j], max(dp[2][k_opt-1], dp[3][j-k_opt]) + 1);
   }

   • ​​原理​​：利用 dp[2][k-1] 递增和 dp[3][j-k] 递减的特性
   • ​​效果​​：时间复杂度降为 O(n)

2. ​​空间优化​​：

   int dp_prev[MAX_N]; // 存储i-1层的结果
   int dp_curr[MAX_N]; // 存储当前层结果

   • 只需保存前一层状态，空间复杂度降为 O(n)

3. ​​二分搜索优化​​：

   int left = 1, right = j;
   while (left < right) {int mid = (left + right) / 2;if (dp[2][mid-1] < dp[3][j-mid]) {left = mid + 1;} else {right = mid;}
   }

   • 在内部循环中使用二分查找最优 k
   • 时间复杂度降为 O(n log n)

最终优化代码

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;const int MAX_N = 10005;int main() {int n;cin >> n;int dp1[MAX_N] = {0}; // 1部手机int dp2[MAX_N] = {0}; // 2部手机int dp3[MAX_N] = {0}; // 3部手机// 初始化for (int i = 1; i <= n; i++) {dp1[i] = i;}// 双指针优化二部手机int k2 = 1;for (int j = 1; j <= n; j++) {while (k2 < j && dp1[k2] < dp2[j - k2]) {k2++;}dp2[j] = max(dp1[k2-1], dp2[j-k2]) + 1;}// 双指针优化三部手机int k3 = 1;for (int j = 1; j <= n; j++) {while (k3 < j && dp2[k3] < dp3[j - k3]) {k3++;}dp3[j] = max(dp2[k3-1], dp3[j-k3]) + 1;}cout << dp3[n] << endl;return 0;
}

这个优化版本的时间复杂度为 O(n)，空间复杂度为 O(n)，能够在 0.1 秒内处理 n=10000 的最大边界情况，满足题目要求。