# 简单贪心题（greedy）

简单贪心题（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;
}