大楼扔鸡蛋

题意

可曾听闻过——大楼扔鸡蛋？

某个品种的鸡蛋，有一个硬度值 $H(0\leq H \leq N)$，相当于在第 $H$ 层会裂开来，而从 $0$ 到 $H-1$ 不会碎，我们现在要求出这个 $H$，但我们只有最朴素的方法——

出题人：“给你 $K$ 个鸡蛋，你在最坏的情况下要扔多少次？但是有一点，到时候不要说不出来，否则…”

没错，这道题就是一个大楼扔鸡蛋，但是前往 Spoj 上之后，你就会发现…

$T\leq 10^{5}$，$N,K\leq 10^{18}$

这是什么数据啊？

别急，让我们慢慢地…从最朴素开始。

分析

我们先从最简单的地方，也就是 spoj 上的 subtask 1 分析。

当 $K=1$ 时，显而易见，如果我们想要求出来鸡蛋的硬度，我们必须一层一层试，最好情况当然是在第一层时就碎了，但最坏情况下，我们要一直试到顶层才能知道硬度，所以最坏情况显然是 $N$ 次。

$K=2$ 时，情况有些微妙了，能不能用比较快的方法得到呢？

• 第一种思路：二分

每次从可能的中间开始扔，碎裂后扔下边的层，否则扔上边的，这样做的话，最好情况是 $log N$ 次，但最坏情况依旧不乐观，是 $\left \lfloor \dfrac{N}{2}\right \rfloor$ 的次数，我们不能接受。

• 第二种思路：等间隔丢法

我们可以将 $N$ 层楼分解成几个区间，每次从区间的最上端扔，碎了就遍历整个区间，假设我们把区间分为 $G$ 个，则每个区间长度为 $\dfrac {N}{G}$，最坏情况下，则需要 $G+\dfrac{N}{G}$（粗略估计）次，当 $G$ 足够优秀时，确实比二分快了不少。

• 第三种思路：不等间隔丢法

既然等间隔比较优秀，那么我们是不是把这种方法再优化一下就可以了？答案是肯定的，我们将区间划分为一些不等的间隔，这样在下边碎的时候逐个遍历的次数多，在上边的次数少，实际上就得到了 $K=2$ 时最优秀的解决方法。

找个方法吧，比如 $N=8$ 时，我们可以找一下高斯，让他帮忙解决一下：

我们用高斯的公式，把八个高度分为 $4,3,1$，这样无论在红线标记的哪个位置碎掉，实际上都是需要 $4$ 次尝试，于是我们得出，当 $K=2$ 时，只需要求出一个 $i$，使得 $\dfrac{i*(i+1)}{2}\geq N$ 即可。

至此，我们完成了这道题的十分！（好耶！）

下一个！

$N,K\leq 10^{3}$

哎呀，现在 $K$ 不等于 $2$ 了，这可如何是好？

没关系，我们慢慢来。

• 动态规划

假设我们最终的答案为 $dp_{N,K}$，其中 $dp_{i,j}$ 表示在 $i$ 的限度内，拥有 $j$ 颗蛋时的最小尝试次数。

我们的 $K$ 颗蛋，实际上是为我们分隔子问题而用的，假设我们拥有 $b$ 颗鸡蛋，且硬度最大值为 $a$，我们试着在第 $i$ 层扔下鸡蛋，如果碎了，那么接下来的次数就是 $dp_{i-1,b-1}$，如果没碎呢，接下来的次数就是 $dp_{a-i,b}$。

对于 $a-i$ 的得法，如果没碎，实际上就将整个区间的下界缩小了 $i$，于是整个区间长度变为 $a-i$，自然就可以从 $b-i$ 中得到。

好的，因为要求的是最坏情况，所以应该是这两者的最大值，于是转移方程便显而易见了。

$dp_{a,b}=\min(\underset{1 \leq i \leq N}{\max}(dp_{a-i,b},dp_{i-1,b-1}))+1$

时间复杂度 $O(KN^{2})$。

有了这个式子，我们再想想，对于 $\underset{1 \leq i \leq N}{\max}(dp_{a-i,b},dp_{i-1,b-1})$，前一个一定是单调递增的，因为可能楼层在不断增大，后一个一定是单调递减的，因为可能楼层在不断减小，而且这两个值的最大值一定会有一个最低点，因此我们可以用二分的方法，找到这两个值的波谷，从而降低时间复杂度。

一个 $O(N)$ 转为了二分枚举，因此时间复杂度 $O(KNlogN)$，这个算法的查询是 $O(1)$ 的，于是，我们就可以通过 subtask2。

但是这个算法还可以再次优化，我们尝试魔改这个 $dp$ 数组，也就是改变状态，
$dp_{i,j}$ 代表拥有 $j$ 颗鸡蛋，允许扔 $i$ 次时最少能测出多少层的硬度，比如说 $dp_{10,1}$ 的值便是 $10$，因为一层一层扔最大到十。

既然状态改变了，那么方程也应该随之改变，我们再想想，如果扔下来，碎了，那么硬度值便在楼下，这个值为 $dp_{i-1,j-1}$，$i$ 是次数减 $1$，$j$ 是因为鸡蛋碎了，所以减 $1$。如果没碎，在楼上的话，这个值为 $dp_{i-1,j}$，原因同上，因为这样做也确定了当前楼层，所以总共便是：

$dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}+1$

我们只需要枚举 $i$，直到 $dp_{i,K}\geq N$，此时的 $i$ 便是答案。

时间复杂度 $O(KN)$，已经十分美观了。

无论怎样，直至现在，我们还是没能通过最大的数据，于是我们开启头脑风暴，将这个过程深入分析一下。

我们换一种方式表示 $dp_{i,j}$，设 $f_{i,j}=dp_{i,j}-dp_{i,j-1}$，所以：

$\begin{aligned} f_{i,j}&=dp_{i-1,j-1}+dp_{i-1,j}+1-(dp_{i-1,j-2}+dp_{i-1,j-1}+1) \\&=f_{i-1,j}+f_{i-1,j-1} \end{aligned}$

一个值，由上边和左上得到，你想到了什么？

杨辉三角！

因此，我们用 $Y_{r,c}$ 表示第 $r$ 行第 $c$ 列的值，而且我们知道 $Y_{r,c}=C_{r}^{c}$

所以：

$Y_{i,j}=C_{i}^{j+1}$

$dp_{i,j}=\underset{1 \leq x \leq K}{\sum}Y_{i,x}=\underset{1 \leq x \leq K}{\sum}C_{i}^{x}$

我们感性理解这个式子：

每次扔鸡蛋，只有碎与不碎两种情况，因此，最终我们会得到一个 $01$ 序列，$0$ 代表没有碎，$1$ 代表碎了，碎了 $0$ 次的方案数为 $C_{i}^{0}$，碎了 $1$ 次的方案数为 $C_{i}^{1}$，以此类推，最终总方案数，也就是得到的结果，便是 $\sum_{1 \leq x \leq K }C_{i}^{x}$。

于是，我们的最终目的便成为了：找到一个最小的 $i$，使得 $dp_{i,K} \geq N$，看起来没什么变化，但是使用这种方法，我们不需要再存储 $dp$ 数组，而且对于更大的 $i$，显然有 $dp_{i,K} \geq N$，我们又需要求最小的 $i$ 值，所以 $i$ 直接二分求即可。

对于这种算法，时间复杂度为 $O(KlogN)$，看上去似乎不够，但我们发现，当 $K$ 足够大时，可以简单认为直接二分即可，这样对于 $N$ 的最大值$10^{18}$，$K$ 的最大值便是 $60$，因此，如果 $K$ 的值在 $60$ 以上，直接输出 $logN$ 即可（想一想如何取整），总体复杂度为 $O(TKlogN)$，能够通过本题，而且由于 $N$ 非常大，所以一定要考虑精度问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include<iostream>
#include<cmath>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
long long read()
{
	char c=getchar();
	long long x=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
long long f(long long x,long long k,long long n) {
		long double ans=0,r=1;
		long double p=n;
		for (long long i = 1; i <= k; i++) {
			r = r*(long double)(x-i+1);
			r = r / i;
			ans += r;
//			printf("%lf %lf %lf\n",ans,r,p);
			if (ans >=p) return 1;
			}
			return 0;
			}
long long solve(long long k,long long n) {
		long long l = 1, r = n;
		while (l < r) {
			long long m = (l + r)/2;
			if (!f(m, k, n)) l = m + 1;
			else r = m;
		}
		return l;
	}
int main()
{
//	freopen("1.txt","r",stdin);
//	freopen("2.txt","w",stdout);
	long long T=read();
	while(T--)
	{
		bool flag=0;
		long long n,k,c=0;
		long long ss=1;
		n=read(),k=read();
//		cout<<n.size()<<" "<<c.size()<<endl;
//		cout<<(n==c)<<endl;
		if(n==0)
		{
			cout<<0<<endl;
			continue;
		}
//		cout<<poww(2,60)<<endl;
			for(long long i=1;i<=k;i+=1)
			{
				ss*=2;
//				cout<<i<<" "<<ss<<endl;
				if(ss>n)
				{
					flag=1;
					cout<<i<<endl;
					break;
				}
			}
		if(flag) continue;
		cout<<solve(k,n)<<endl;
	}
}

时间紧迫，如有错误，敬请指出！