eagleeggs|eagleeggs.in|eagleeggs.out
题目描述：
共有N个硬度相同的鹰蛋，硬度是一个整数（并且已知其不大于H），表示这个蛋从天上掉下来不摔碎的最大高度。为了找出这个最大高度，可以进行一些试验，每次实验把一个鹰蛋从一定高度扔下，根据这个鹰蛋是否摔碎可以知道真实的硬度是否大于你抛下的高度。
求在最坏情况下试验的最少次数。
输入格式：
一行两个整数N，H
输出格式：
一行一个整数，表示硬度
样例输入：
2
5
样例输出：
3
数据范围：
30%
N<=1000 H<=1000
对另外30%
N<=100000 H<=100000
对所有数据N<=10^9
H<=10^9
觉得课上dp讲的太复杂了，用组合数一下就做出来了。
注意一下爆int的处理
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define PROB "eagleeggs"
#define MAXN 10100
#define INF 0x3f3f3f3f
typedef unsigned long long qword;
qword dp[MAXN][];
qword c(int x,int y)//x<=30
{
if (y==)return x;
if (y==)return x*(x-)/;
if (y>x)return ;
dp[][]=;
int i,j;
for (i=;i<=x;i++)
{
dp[i][]=i;
for (j=;j<=x;j++)
{
dp[i][j]=dp[i-][j]+dp[i-][j-];
}
if (dp[i][y]>=INF)return INF;
}
return dp[x][y];
}
qword hgt(int n,int t)
{
qword ans=;
qword temp=;
int i,j;
for (i=n;i>;i--)
{
temp=c(t,i);
if (temp==INF)return INF;
ans+=temp;
if (ans>INF)return INF;
}
return ans;
}
int main()
{
freopen(PROB".in","r",stdin);
freopen(PROB".out","w",stdout);
int i,j,k;
int n;
qword h;
cin>>n>>h;
int l=,r=;
int mid;
if (n==)
{
printf("%d\n",h);
return ;
}
if (n>||(<<n)>=h)
{
printf("%d\n",(int)ceil(log2(h)));
return ;
}
if (n!=)r=;
while (l+<r)
{
mid=(l+r)/;
if (h<=hgt(n,mid))
{
r=mid;
}else
{
l=mid;
}
}
printf("%d\n",r);
}