题目描述

牛油果是一种神秘的水果，其具有一个坚固程度x≥0x\geq 0x≥0：即从高度不超过xxx米的地方掉下来都不会受损，否则就会破碎。

现在有nnn个牛油果可以用来做实验，如果某个牛油果在一次实验中破碎了就不能继续做实验，否则就可以继续拿来做实验。

假设给出的牛油果坚固程度相同，且已知它们的坚固程度不超过mmm，现在要求最坏情况下至少做多少次实验可以得知它们的坚固程度。

输入格式

一行一个ttt，表示数据组数。

一行两个正整数n,mn,mn,m。

输出格式

输出ttt行，第iii行一个正整数表示第iii组数据的答案。

样例输入

2
1 2
2 10

样例输出

2
4

数据规模

对于10%10\%10%的数据，n,m,t≤10n,m,t\leq 10n,m,t≤10
对于30%30\%30%的数据，n,m,t≤50n,m,t\leq 50n,m,t≤50
对于60%60\%60%的数据，n,m,t≤500n,m,t\leq 500n,m,t≤500
对于100%100\%100%的数据，n,m,t≤5000n,m,t\leq 5000n,m,t≤5000

题解

设fi,jf_{i,j}fi,j​表示有iii个牛油果，坚固程度不超过jjj的最少的实验次数，fff的初值为fi,0=0f_{i,0}=0fi,0​=0，f0,i=+∞f_{0,i}=+\inftyf0,i​=+∞。

考虑转移，假设此时将一个牛油果从kkk米高的地方扔下来，则

• 如果碎了，那么牛油果的坚固程度不超过k−1k-1k−1，还剩i−1i-1i−1个牛油果，则需要的次数为fi−1,k−1+1f_{i-1,k-1}+1fi−1,k−1​+1
• 如果没碎，那么牛油果的坚固程度在kkk到jjj之间，还剩iii个牛油果，在kkk到jjj之间测试坚固程度等价于在000到j−kj-kj−k之间测试坚固程度，所以需要的次数为fi,j−k+1f_{i,j-k}+1fi,j−k​+1

所以转移式为

fi,j=min⁡k=1j{max⁡(fi−1,k−1,fi,j−k)+1}f_{i,j}=\min\limits_{k=1}^j\{\max(f_{i-1,k-1},f_{i,j-k})+1\}fi,j​=k=1minj​{max(fi−1,k−1​,fi,j−k​)+1}

得到所有的fff值，即可O(1)O(1)O(1)输出答案。

这样做的时间复杂度为O(n3)O(n^3)O(n3)，会TLE。

code

#include
using namespace std;
const int N=5000;
int t,n,m,now;
long long f[5005][5005]; 
int main()
{f[0][0]=0;for(int i=1;i<=N;i++) f[0][i]=1e18;for(int i=1;i<=N;i++){f[i][0]=0;for(int j=1;j<=N;j++){f[i][j]=1e18;for(int k=1;k<=j;k++){f[i][j]=min(f[i][j],max(f[i][j-k],f[i-1][k-1])+1);}}}scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);printf("%lld\n",f[n][m]);}return 0;
}

我们考虑优化。

对于求fi,jf_{i,j}fi,j​，需要用到的数为fi−1,k−1f_{i-1,k-1}fi−1,k−1​和fi,j−kf_{i,j-k}fi,j−k​，其中1≤k≤j1\leq k\leq j1≤k≤j。我们发现随着kkk的增大，fi−1,k−1f_{i-1,k-1}fi−1,k−1​单调递增（不严格），fi,j−kf_{i,j-k}fi,j−k​单调递减（不严格）。那么它们的图象大致如下

jjj增加了111之后，fi−1,k−1f_{i-1,k-1}fi−1,k−1​部分不变，fi,j−kf_{i,j-k}fi,j−k​向右平移一位。我们可以发现，fi,j+1f_{i,j+1}fi,j+1​选择的kkk一定在fi,jf_{i,j}fi,j​选择的kkk的右边（不严格），所以kkk的枚举可以省去。

时间复杂度为O(n2)O(n^2)O(n2)。

code

#include
using namespace std;
const int N=5000;
int t,n,m,now;
long long f[5005][5005]; 
int main()
{
//	f[0][0]=0;
//	for(int i=1;i<=N;i++) f[0][i]=1e18;
//	for(int i=1;i<=N;i++){
//		f[i][0]=0;
//		for(int j=1;j<=N;j++){
//			f[i][j]=1e18;
//			for(int k=1;k<=j;k++){
//				f[i][j]=min(f[i][j],max(f[i][j-k],f[i-1][k-1])+1);
//			}
//		}
//	}f[0][0]=0;for(int i=1;i<=N;i++) f[0][i]=1e18;for(int i=1;i<=N;i++){f[i][0]=0;now=0;for(int j=1;j<=N;j++){while(now+1<=j-1&&max(f[i][now+1],f[i-1][j-1-now-1])<=max(f[i][now],f[i-1][j-1-now])) ++now;f[i][j]=max(f[i][now],f[i-1][j-1-now])+1;}}scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);printf("%lld\n",f[n][m]);}fclose(stdin);fclose(stdout);return 0;
}

其实还有一个小优化，因为我们可以二分查找坚固程度，所以最多只需要log⁡m\log mlogm次即可得出牛油果的坚固程度，log⁡m≤13\log m\leq 13logm≤13。也就是说，我们的iii只需从111枚举到131313即可，不需要上述的优化。

时间复杂度为O(13n2)O(13n^2)O(13n2)，勉强能过。

code

#include
using namespace std;
const int N=5000;
int t,n,m,now;
long long f[15][5005]; 
int main()
{f[0][0]=0;for(int i=1;i<=N;i++) f[0][i]=1e18;for(int i=1;i<=13;i++){f[i][0]=0;for(int j=1;j<=N;j++){f[i][j]=1e18;for(int k=1;k<=j;k++){f[i][j]=min(f[i][j],max(f[i][j-k],f[i-1][k-1])+1);}}}scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);if(n>13) n=13;printf("%lld\n",f[n][m]);}return 0;
}

如果你将两种优化方法结合，那么你的代码会跑得飞快。

时间复杂度为O(13n)O(13n)O(13n)。

#include
using namespace std;
const int N=5000;
int t,n,m,now;
long long f[15][5005]; 
int main()
{f[0][0]=0;for(int i=1;i<=13;i++) f[0][i]=1e18;for(int i=1;i<=13;i++){f[i][0]=0;now=0;for(int j=1;j<=N;j++){while(now+1<=j-1&&max(f[i][now+1],f[i-1][j-1-now-1])<=max(f[i][now],f[i-1][j-1-now])) ++now;f[i][j]=max(f[i][now],f[i-1][j-1-now])+1;}}scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);if(n>13) n=13;printf("%lld\n",f[n][m]);}fclose(stdin);fclose(stdout);return 0;
}