SP25338 NPC2015E - Eefun Plays LOL 题解

· · 题解

题意

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

某个品种的鸡蛋，有一个硬度值 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 次。

- **第一种思路：二分** 每次从可能的中间开始扔，碎裂后扔下边的层，否则扔上边的，这样做的话，最好情况是 $log N$ 次，但最坏情况依旧不乐观，是 $\left \lfloor \dfrac{N}{2}\right \rfloor$ 的次数，我们不能接受。 - **第二种思路：等间隔丢法** 我们可以将 $N$ 层楼分解成几个区间，每次从区间的最上端扔，碎了就遍历整个区间，假设我们把区间分为 $G$ 个，则每个区间长度为 $\dfrac {N}{G}$，最坏情况下，则需要 $G+\dfrac{N}{G}$（粗略估计）次，当 $G$ 足够优秀时，确实比二分快了不少。 - **第三种思路：不等间隔丢法** 既然等间隔比较优秀，那么我们是不是把这种方法再优化一下就可以了？答案是肯定的，我们将区间划分为一些不等的间隔，这样在下边碎的时候逐个遍历的次数多，在上边的次数少，实际上就得到了 $K=2$ 时最优秀的解决方法。 找个方法吧，比如 $N=8$ 时，我们可以找一下高斯，让他帮忙解决一下： ![](https://cdn.luogu.com.cn/upload/image_hosting/u2n1p014.png) 我们用高斯的公式，把八个高度分为 $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-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 非常大，所以一定要考虑精度问题。

代码

#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;
    }
}

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