【題目描述】

最近XX公司舉辦了一個奇怪的比賽：雞蛋硬度之王爭霸賽。參賽者是來自世界各地的母雞，比賽的內容是看誰下的蛋最硬，更奇怪的是XX公司并不使用什么精密儀器來測量蛋的硬度，他們采用了一種最老土的辦法--從高度扔雞蛋--來測試雞蛋的硬度，如果一次母雞下的蛋從高樓的第a層摔下來沒摔破，但是從a+1層摔下來時摔破了，那么就說這只母雞的雞蛋的硬度是a。你當然可以找出各種理由說明這種方法不科學，比如同一只母雞下的蛋硬度可能不一樣等等，但是這不影響XX公司的爭霸賽，因為他們只是為了吸引大家的眼球，一個個雞蛋從100 層的高樓上掉下來的時候，這情景還是能吸引很多人駐足觀看的，當然，XX公司也絕不會忘記在高樓上掛一條幅，寫上“XX公司”的字樣--這比賽不過是XX 公司的一個另類廣告而已。

勤于思考的小A總是能從一件事情中發現一個數學問題，這件事也不例外。“假如有很多同樣硬度的雞蛋，那么我可以用二分的辦法用最少的次數測出雞蛋的硬度”，小A對自己的這個結論感到很滿意，不過很快麻煩來了，“但是，假如我的雞蛋不夠用呢，比如我只有1個雞蛋，那么我就不得不從第1層樓開始一層一層的扔，最壞情況下我要扔100次。如果有2個雞蛋，那么就從2層樓開始的地方扔……等等，不對，好像應該從1/3的地方開始扔才對，嗯，好像也不一定啊……3個雞蛋怎么辦，4個，5個，更多呢……”，和往常一樣，小A又陷入了一個思維僵局，與其說他是勤于思考，不如說他是喜歡自找麻煩。

好吧，既然麻煩來了，就得有人去解決，小A的麻煩就靠你來解決了：）

【輸入】

輸入包括多組數據，每組數據一行，包含兩個正整數n和m(1≤n≤100,1≤m≤10)，其中n表示樓的高度，m表示你現在擁有的雞蛋個數，這些雞蛋硬度相同（即它們從同樣高的地方掉下來要么都摔碎要么都不碎），并且小于等于n。你可以假定硬度為x的雞蛋從高度小于等于x的地方摔無論如何都不會碎（沒摔碎的雞蛋可以繼續使用），而只要從比x高的地方扔必然會碎。

對每組輸入數據，你可以假定雞蛋的硬度在0至n之間，即在n+1層扔雞蛋一定會碎。

【輸出】

對于每一組輸入，輸出一個整數，表示使用最優策略在最壞情況下所需要的扔雞蛋次數。

【輸入樣例】

100 1
100 2

【輸出樣例】

100
14

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 2520 #define E 1e-12 using namespace std; int f[110][20]; int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j]=i;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)for(int k=2;k<=m;k++)f[i][k]=min(f[i][k],max(f[j-1][k-1],f[i-j][k])+1);cout<<f[n][m]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的鸡蛋的硬度（信息学奥赛一本通-T1300）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。