📅 发布时间：2026/6/19 21:17:57

简单贪心题（greedy）

注意：题面有误，应该为 $n+1$ 层楼，否则数据有误，但题解中视为一共有 $n$ 层楼的情况。

题目描述

你有 $k$ 个一模一样的鸡蛋，一共有 $n$ 层楼，鸡蛋有一个碎裂值 $x$。代表在超过(包含) $x(1\leq x\leq n)$ 层的地方扔鸡蛋鸡蛋会碎掉。

问你在最坏的情况下需要扔几次鸡蛋才能确定碎裂值。答案对 $147744151$ 取模。

数据范围

对于所有数据，$1\le n,k\le 147744151151447741$。

题解

$Sub1$

显然当 $k=1$ 的时候我们只能从第一层不断尝试直到鸡蛋碎裂，但是注意，当我们尝试到 $n-1$ 层时，就可以停止了。原因：

假如鸡蛋碎了，答案就是 $n-1$.
假如鸡蛋没碎，答案就是 $n$.

$Sub2$

我们有一个最优策略：

对于第一个鸡蛋，我们来缩小第二个鸡蛋的枚举范围。而第二个鸡蛋用来枚举（详见 $Sub1$）。

我们尝试动态规划解决。

设 $f_x$ 为用两个鸡蛋丢了 $x$ 次能判断鸡蛋碎裂度的最大高度。那么答案就是第一个 $x$ 使得 $f_x\ge n$.

我们考虑转移，发现有：

\[f_x=f_{x-1}+x \]

那么有：

\[f_x=\frac{x(x-1)}{2} \]

转移解释：

考虑 $f_x$ 的后续情况，就是这个蛋碎了或者没碎。

假如碎了，那么变成 $Sub1$，提供了后面的 $+x$.
假如没碎，那么就是子问题。

然后发现这不是二次函数求解吗，蛙趣，解方程就行了。时间复杂度 $O(1)$.

$Sub3$

注意到二分需要 $\left \lceil \log_2 (x+1) \right \rceil $ 个鸡蛋，大于这个界都可以二分，但是一样的。

而 $147744151$ 显然大于这个界。所以这个时候我们就可以直接二分楼层，所以答案其实也就是 $\left \lceil \log_2 (x+1) \right \rceil $.

$Sub4-8$

和正解没区别，直接讲正解。

正解

发现样例 $2$ 很有意思，其实就是除了 $k=1$ 时候的答案上界（约为 $10^8$）。而且这个数据范围是可以枚举的，我们思考对答案直接枚举，接着你会想判断答案可否选择，接着就是二分判断答案。

$Sub2$ 提示我们用动态规划解决，但是 $n$ 太大了，考虑用继续数学方式判断。

先给出一个结论：设 $f_{i,j}$ 为丢了 $i$ 次，有 $j$ 个鸡蛋的最大能判断的鸡蛋碎裂度，那么有：

\[\large f_{i,j}=\sum^{j}_{x=1}C^{x}_{i} \]

证明：

首先类似 $Sub2$ 写出转移：

\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j}+1 \]

证明也类似，不证了。

这个东西很像杨辉三角的转移，考虑数学归纳法，当然考试的时候是推广 $Sub2$ 的结论，递推可写出上面的式子，只不过这样更好证明：

代入归纳假设：

\[f_{i,j} = \sum_{x=1}^{j-1} \binom{i-1}{x} + \sum_{x=1}^{j} \binom{i-1}{x} + 1 \]

合并求和项：

\[f_{i,j} = 2 \sum_{x=1}^{j-1} \binom{i-1}{x} + \binom{i-1}{j} + 1 \]

另一方面，考虑二项式系数的性质：

\[\binom{i}{x} = \binom{i-1}{x-1} + \binom{i-1}{x} \]

因此：

\[\sum_{x=1}^{j} \binom{i}{x} = \sum_{x=1}^{j} \left( \binom{i-1}{x-1} + \binom{i-1}{x} \right) \]

拆分求和：

\[= \sum_{x=1}^{j} \binom{i-1}{x-1} + \sum_{x=1}^{j} \binom{i-1}{x} \]

在第一个求和中，令 $y = x-1$，则：

\[\sum_{x=1}^{j} \binom{i-1}{x-1} = \sum_{y=0}^{j-1} \binom{i-1}{y} = 1 + \sum_{y=1}^{j-1} \binom{i-1}{y} \]

第二个求和为：

\[\sum_{x=1}^{j} \binom{i-1}{x} = \sum_{x=1}^{j-1} \binom{i-1}{x} + \binom{i-1}{j} \]

代入得：

\[\sum_{x=1}^{j} \binom{i}{x} = 1 + \sum_{y=1}^{j-1} \binom{i-1}{y} + \sum_{x=1}^{j-1} \binom{i-1}{x} + \binom{i-1}{j} = 1 + 2 \sum_{x=1}^{j-1} \binom{i-1}{x} + \binom{i-1}{j} \]

这与 $f_{i,j}$ 的表达式一致，故：

\[f_{i,j} = \sum_{x=1}^{j} \binom{i}{x} \]

写完发现我们可以 $O(k)$ 判断答案。

接下来发现这不是就是二分板子吗，蛙趣，写完了。

时间复杂度 $O(k\log n)$，加上前面 $Sub3$ 的 $k\ge \left \lceil \log_2 (x+1) \right \rceil $ 的部分，可以知道复杂度上界是 $O(\log^2n)$。

code:

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 2005,MOD = 147744151;
long long n,m;
bool check(int x){int ans = 1,sum = 0;for(int i=1;i<=m;i++){ans = ans*(x-i+1)/i;sum += ans;if(sum>=n) return 0;}return 1;
}
signed main(){freopen("greedy.in","r",stdin);freopen("greedy.out","w",stdout);cin>>n>>m;if(m>log2(n)){cout<<(long long)log2(n) + 1;return 0;}int L = 0,R = n,ans = 0;while(L<=R){int mid = (L+R)>>1;if(check(mid)) L = mid+1;else ans = mid,R = mid-1;}cout<<(long long)(ans%MOD);return 0;
}

# 简单贪心题（greedy）

简单贪心题（greedy）

注意：题面有误，应该为 \(n+1\) 层楼，否则数据有误，但题解中视为一共有 \(n\) 层楼的情况。

题目描述

数据范围

题解

\(Sub1\)

\(Sub2\)

\(Sub3\)

\(Sub4-8\)

正解