首页 > 试题广场 >

多多的魔术盒子

[编程题]多多的魔术盒子
  • 热度指数：6459 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
多多鸡有N个魔术盒子（编号1～N），其中编号为i的盒子里有i个球。
多多鸡让皮皮虾每次选择一个数字X（1 <= X <= N），多多鸡就会把球数量大于等于X个的盒子里的球减少X个。
通过观察，皮皮虾已经掌握了其中的奥秘，并且发现只要通过一定的操作顺序，可以用最少的次数将所有盒子里的球变没。
那么请问聪明的你，是否已经知道了应该如何操作呢？



输入描述:
第一行，有1个整数T，表示测试用例的组数。
（1 <= T <= 100）
接下来T行，每行1个整数N，表示有N个魔术盒子。
（1 <= N <= 1,000,000,000）


输出描述:
共T行，每行1个整数，表示要将所有盒子的球变没，最少需要进行多少次操作。
示例1

输入

3
1
2
5

输出

1
2
3
算法知识视频讲解
添加回答
Python
Nowdata头像 Nowdata 
def steps(n):
    if n<=0:
        return -1
    if n==1:
        return 1
    if n==2:
        return 2
    else:
        return steps(int(n/2))+1
T=input()
while True:
    try:
        n=int(input())
        res=steps(n)
        print(res)
    except:
        break

发表于 2021-04-26 23:45:46 回复(0)
Python
想去东北泡澡的芝士在刷题头像 想去东北泡澡的芝士在刷题 
import math
t = int(input())
for i in range(t):
    n = int(input())
    print(int(math.log(n, 2)) + 1)
二分，用1234  12345这种作为例子规律一下子就会出来
编辑于 2020-08-08 13:57:59 回复(0)
Python
我不想当大白菜头像 我不想当大白菜

分析

  • 实质上是一道数学题，只需要考虑把最大值N减到零需要的次数，最优方案为每次减去ceil(N/2)的值，当其为零的时候别的值也都被减到零了。
    之后看了别的回答，确实直接取log或者位操作更好，我只看到了第一层 
    from math import ceil
def calc_times(N):
  count = 0
  while N:
      val = ceil(N/2)
      N -= val
      count += 1
  return count
def main():
  T = int(input())
  for i in range(T):
      N = int(input())
      print(calc_times(N))
main()
发表于 2020-07-09 12:47:04 回复(0)
Python
鱼飞头像 鱼飞 
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
m = max(a)
dp = [0]*(m+1)
for i in range(1,m+1):
    dp[i] = dp[i//2] + 1
for i in range(n):
    print(dp[a[i]])
我这凭什么不对啊 
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
def f(n):
    res = 1
    while n > 1:
        n//=2
        res+=1
    return res
for i in a:
    print(f(i))
我真的吐了，用了个**方法反而对了，前面那个不管是时间还是空间都要优于这个，反而不通过，凭啥啊
原来是空间超限，但是上面那个时间会优很多

编辑于 2020-06-02 00:49:09 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 前端工程师 算法工程师 PHP工程师 2020 拼多多集团-PDD 大数据开发工程师 Java工程师 信息技术岗
上传者：小小
难度：
4条回答 10463浏览

热门推荐

通过挑战的用户

相关试题

多多的魔术盒子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号