题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

// 明确三个关键值：测量的长度，用的鸡蛋(注意：还有碎的鸡蛋)，扔鸡蛋测的次数
/
f[i][j]:所有测量长度是i(只跟区间长度即高度的绝对值有关)且有j个鸡蛋的测量方案的集合，求最坏情况下测的次数的最小值
这里是最多用j个鸡蛋，所以最后一个即第j个鸡蛋，用不用分两类：没有用过第j个和用过第j个。
用第j个鸡蛋和第j个鸡蛋碎了是两码事，用第j个鸡蛋可能碎了也可能没碎
/

// 方法一：O(n^2 * m)
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]
// #include [HTML_REMOVED]

// using namespace std;

// const int N = 110, M = 11;

// int n, m;
// int f[N][M];

// int main() {
// while (cin >> n >> m) {
// for (int i = 1; i <= n; i ) f[i][1] = i;
// for (int i = 1; i <= m; i ) f[1][i] = 1;

// for (int i = 2; i <= n; i )
// for (int j = 2; j <= m; j ) {
// f[i][j] = f[i][j - 1];
// for (int k = 1; k <= i; k ++)
/ 凡是不能控制的情况取最坏，凡是可以控制的情况取最好
因为虽然可以控制k在哪儿测，但是不能控制在k测的结果碎不碎
k属于最坏情况，所以取最大值，选k碎不碎这两种情况的最大值但是选所有k里边的最小值
最后第j个鸡蛋可以选择用或者不用，所以选择最小值
/
// f[i][j] = min(f[i][j], max(f[k - 1][j - 1], f[i - k][j]) + 1);
// }
// cout << f[n][m] << endl;
// }
// return 0;
// }

// 方法二：O(nm)
/
f[i][j]:所有(最多)用j个鸡蛋(最多)测i次的测量方案的集合，最多能测量多长的区间
当这个区间累加起来大于n即可
/

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 110, M = 11;

int n, m;
int f[N][M];

int main() {
while (cin >> n >> m) {
// 无需初始化
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= m; j )
// 蛋碎能测多长：f[i - 1][j - 1]，蛋不碎能测多长：f[i - 1][j]
// 两者相加才能求出来最多可以测多长的的区间即高度，因为每次只分鸡蛋碎不碎两种情况
// 所有考虑所有情况下即包含最坏情况，可以测多长的长度。
f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + 1;
if (f[i][m] >= n) { // 一定有解，因为当i循环到n的时候，能测n层
printf(“%d\n”, i);
break;
}
}
}
return 0;
}

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla