我要招人

去企业版

首页 > 试题广场 >

丢棋子问题

[编程题]丢棋子问题

热度指数：19354 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。

给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。

数据范围： $1 \le i \le n ,k \le 10^6$

要求：空间复杂度 $O(k)$ ，时间复杂度 $O(km)$ (m是最终返回的结果)

示例1

输入

10,1

输出

说明

因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次

示例2

输入

3,2

输出

说明

先在2层扔1棵棋子，如果碎了，试第1层，如果没碎，试第3层

示例3

输入

105,2

输出

说明

第一个棋子先在14层扔，碎了则用仅存的一个棋子试1~13层
若没碎，第一个棋子继续在27层扔，碎了则用仅存的一个棋子试15~26层
若没碎，第一个棋子继续在39层扔，碎了则用仅存的一个棋子试28~38层
若没碎，第一个棋子继续在50层扔，碎了则用仅存的一个棋子试40~49层
若没碎，第一个棋子继续在60层扔，碎了则用仅存的一个棋子试51~59层
若没碎，第一个棋子继续在69层扔，碎了则用仅存的一个棋子试61~68层
若没碎，第一个棋子继续在77层扔，碎了则用仅存的一个棋子试70~76层
若没碎，第一个棋子继续在84层扔，碎了则用仅存的一个棋子试78~83层
若没碎，第一个棋子继续在90层扔，碎了则用仅存的一个棋子试85~89层
若没碎，第一个棋子继续在95层扔，碎了则用仅存的一个棋子试91~94层
若没碎，第一个棋子继续在99层扔，碎了则用仅存的一个棋子试96~98层
若没碎，第一个棋子继续在102层扔，碎了则用仅存的一个棋子试100、101层
若没碎，第一个棋子继续在104层扔，碎了则用仅存的一个棋子试103层
若没碎，第一个棋子继续在105层扔，若到这一步还没碎，那么105便是结果

备注:

算法知识视频讲解

不会做题的小菜鸡

发表于 2021-07-18 23:57:39

精华题解思路动态规划（k棋n层）：dp(k,n)表示有k个棋子n层楼需要尝试的次数，题干要求的是dp(k,n)的结果，我们现在选择在第i层扔棋子如果棋子碎了，则剩下k-1个棋子，此时找的楼层更新为i-1（低楼层），即应该继续尝试的次数为dp(k-1,i-1) 如果棋子没碎，则剩下k个棋子，此时要找展开全文

棒棒糖🍭201906101800876

发表于 2021-07-16 12:25:06

精华题解 nc87. 丢棋子问题 1. 暴力搜索 (不合要求, TLE) 令f(n, k) 表示n层楼, k个棋子, 在最差情况下的最少实验次数. f(n,k) 有下列性质: 若n=0, 地板上肯定不碎, 不需要任何实验, 故f=0. 若k=1, 只有1个棋子必须逐层操作,在最差情况下第n层楼才摔碎, 需要展开全文

LifelongCode

发表于 2020-12-17 10:28:58

转载 https://www.cnblogs.com/willwuss/p/12256475.html 方法一：暴力算法设P(N,K)的返回值时N层楼时有K个棋子在最差的情况下仍的最少次数。如果N==0，棋子在第0层肯定不会碎，所以P(0, K) = 0;如果K==1，楼层有N层，只有1 展开全文

子夜降晴空

发表于 2021-04-03 20:54:23

核心思路：每次扔的位置都是最佳的，i个棋子扔time次，第1次时，如果碎了，向下可以探测“i-1个棋子扔time-1次”层；如果没碎，向上可以探测“i个棋子扔time-1次”层。上下层数加当前1层即为i个棋子扔time次能探测的最大层数 class Solution { public: in 展开全文

彩笔打野

发表于 2020-12-27 20:32:01

Python解转载一下写的比较好的一个博客https://www.cnblogs.com/willwuss/p/12256475.html简单说以下自己看懂的三种方法1.暴力递归（不建议）设函数F(n,k)返回的是给定n,k所返回的最小试验次数。 Case1:当n=0时，根据已知不用实验即可得展开全文

牛客516598323号

发表于 2020-09-09 23:02:28

二分法，奇数-1对半，偶数对半-1。多于1个棋子最后要-1。这个算法好像有点问题，但是总能通过一部分样例。所以暴力硬编码了……用例通过率: 100.00% 运行时间: 32ms 占用内存: 6524KB。 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # 返回最差展开全文

江南好___

发表于 2021-10-14 23:56:03

描述题目描述一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋展开全文

godhands

发表于 2022-02-12 00:59:54

描述题目描述其实这个题目是一个很经典的题目, 就是我们有NNN层楼, 我们有KKK个物品, 然后我们要计算求解的就是我们在最坏的情况下得到的最小操作数这个我们第一个最简单的想法可能就是一个个的比较去排除, 我们从第一层楼开始我们就是一直向上摔, 看看可不可以摔碎, 如果碎了, 那么正好就是这么展开全文