NKOI 3515 玻璃球

    xiaoxiao2021-08-20  125

    玻璃球

    Time Limit:10000MS  Memory Limit:65536K Total Submit:18 Accepted:15 Case Time Limit:1000MS

    Description

    何老板有k个一模一样的玻璃球,他想知道这些玻璃球的硬度有多大,于是他找了一栋n层高楼来做试验。 一次试验过程是这样的,何老板爬到第x层,然后将一颗玻璃球往下扔(自由落体),如果玻璃球摔坏了,说明它的硬度不超过x。如果玻璃没有摔坏,说明它的硬度至少为x,何老板可以把它捡起来继续测试。 何老板想知道,最少需要试验多少次,才能确定玻璃球的硬度。

    Input

    第一行,两个整数k和n

    Output

    输出一个整数表示答案最少所需试验次数。 63次试验以内都没能得出结果输出“oh no”(没有引号)。

    Sample Input

    样例输入1 2 100 样例输入2 60 1844674407370955161 样例输入3 4 786599

    Sample Output

    样例输出1 14 样例输出2 61 样例输出3 oh no

    Hint

    对于100%的数据,1<=k<=100,1<=n<263

    Source

    uva10934

    我们会先想到二分,确实,在玻璃球足够的情况下二分的确是让步数最小的方案,但是问题就在于题目中限制了球的数量,因此实际上二分是行不通的

    我们发现构造出答案是比较困难的,比如样例一很难直接找出答案(当然答案是可以凑出来的),因此我们考虑用递推找答案

    观察数据范围,我们发现k的范围比较小,n的范围比较大,因此状态中一定有k这个量,一定没有n这个量,然而一维递推无法转移,故增加一维

    于是最终状态为f[i][j],表示选择了i个球,并且将第i个扔下后已经执行了j次的能到达的最高层数

    f[i][j]=f[i-1][j-1]+1+f[i][j-1]

    f[i][j-1]表示第i个球在第j-1次操作的时候用了,但是没爆,因此层数不变,故这一层可以看成地面,

    f[i-1][j-1]+1表示第i-1个球爆了,于是我们在i-1个球的基础上往上走一层(只能走一层),将i-1个球看做在f[i][j-1]丢的

    #include<cstdio> #include<iostream> #define LL long long using namespace std; LL n,k,f[105][65]; int main(){ cin>>k>>n; LL i,j; for(i=0;i<=63;i++)f[1][i]=i; for(i=2;i<=k;i++) for(j=1;j<=63;j++)f[i][j]=f[i-1][j-1]+1+f[i][j-1]; for(j=1;j<=63;j++) if(f[k][j]>=(LL)n)break; if(j==64)puts("oh no"); else cout<<j; }

    转载请注明原文地址: https://ju.6miu.com/read-676719.html

    最新回复(0)