文档章节

OpenJudge7627 鸡蛋的硬度

机智的帝江
 机智的帝江
发布于 2016/10/30 09:56
字数 1159
阅读 15
收藏 0

点击就送屠龙宝刀
描述
最近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

提示

最优策略指在最坏情况下所需要的扔鸡蛋次数最少的策略。
如果只有一个鸡蛋,你只能从第一层开始扔,在最坏的情况下,鸡蛋的硬度是100,所以需要扔100次。如果采用其他策略,你可能无法测出鸡蛋的硬度(比如你第一次在第二层的地方扔,结果碎了,这时你不能确定硬度是0还是1),即在最坏情况下你需要扔无限次,所以第一组数据的答案是100。

首先这不是二分!首先这不是二分!首先这不是二分!不要妄图用二分的思想做!你会发现代码恶心到吐。。(反正我调不出来)
我们用f[i][j]表示i层楼扔j个鸡蛋。那么很容易得出 f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j]+1))
后面的就不用说了。。

#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,dp[1004][15];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0x7f,sizeof(dp));
        for(int i=0;i<=n;i++) dp[i][1]=i;
        for(int i=0;i<=m;i++) dp[0][i]=0;
        for(int i=2;i<=m;i++)
        for(int j=1;j<=n;j++)
        for(int k=1;k<=j;k++)
        dp[j][i]=min(dp[j][i],max(dp[k-1][i-1],dp[j-k][i])+1);
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/52812742

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
2018 年力扣高频算法面试题汇总-难题记录-鸡蛋掉落

题目描述: 你将获得 个鸡蛋,并可以使用一栋从 到 共有 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 ,满足 任何从高于 的楼层落下的鸡蛋...

chenjx85
03/13
0
0
Spark FPGrowth关联规则算法

Spark.mllib 提供并行FP-growth算法,这个算法属于关联规则算法【关联规则:两不相交的非空集合A、B,如果A=>B,就说A=>B是一条关联规则,常提及的{啤酒}-->{尿布}就是一条关联规则】,经常用...

penngo
03/11
250
0
多线程通信

生产者/消费者模式是一个经典的线程同步以及通信的模型。 假设有这样一种情况,有一个盘子,盘子里只能放一个鸡蛋,A线程专门往盘子里放鸡蛋,如果盘子里有鸡蛋,则一直等到盘子里没鸡蛋,B...

Heinrich_Chen
2016/01/21
160
0
这鸡蛋真难吃

有些人的逻辑是很奇怪的。 网友若昔难得就归纳出了几种。如此经典的内容,我一定要转载, 希望大家集思广益,一起来补充。 ============= A:这鸡蛋真难吃。 B:隔壁家那鸭蛋更难吃,你咋不说...

阮一峰
2008/07/26
0
0
动态规划法(六)鸡蛋掉落问题(一)(egg dropping problem)

  继续讲故事~~   这天,丁丁正走在路上,欣赏着路边迷人的城市风景,突然发现前面的大楼前围了一波吃瓜群众。他好奇地凑上前去,想一探究竟,看看到底发生了什么事情。   原来本市的一...

jclian91
2018/06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

vue中eventBus的使用

使用场景: 1、兄弟组件的通信,父子组件的通信 2、不同路由的通信 针对兄弟组件的通信,父子组件的通信 新建bus.js文件 import Vue from 'vue' var bus = new Vue() export default bus 在需...

tianyawhl
17分钟前
4
0
C# DBHelper

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Data;using System.Data.SqlClient;using System.Windows.Forms;namesp......

vga
20分钟前
3
0
Spring Boot中@ConditionalOnProperty使用详解

在Spring Boot的自动配置中经常看到@ConditionalOnProperty注解的使用,本篇文章带大家来了解一下该注解的功能。 Spring Boot中的使用 在Spring Boot的源码中,比如涉及到Http编码的自动配置...

程序新视界
21分钟前
6
0
centos7下安装mysql(完整配置)

https://blog.csdn.net/baidu_32872293/article/details/80557668

为何不可1995
23分钟前
3
0
如何从零到一设计一个MQ消息队列

消息队列整体设计思路 主要是设计一个整体的消息被消费的数据流。 这里会涉及到:消息生产Producer、Broker(消息服务端)、消息消费者Consumer。 1.Producer(消息生产者):发送消息到Broker。...

一只会编程的狼
29分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部