首页 > 试题广场 > 多多的魔术盒子
[编程题]多多的魔术盒子
  • 热度指数:4728 时间限制: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

CSDN [编程题]多多的魔术盒子

这道题最容易想到的就是不停从中值减少,我也是这样的解法。

@牛客625413878号的代码非常简洁。数字转二进制,位数就是结果,太秀了,不发出来可惜了。
已经提醒本人写题解,等他写了我就删除这部分。

n = int(input())

for i in range(n):
    x = int(input())
    print(len(bin(x))-2)

这是我的代码。

package main

import "fmt"

func main() {
    var t,n int
    fmt.Scan(&t)
    for i:=0;i<t;i++{
        fmt.Scan(&n)
        ans:=1
        for ;n>1;n/=2{
            ans++
        }
        fmt.Println(ans)
    }
}
发表于 2020-05-19 17:24:12 回复(5)
要用最少的次数把所有盒子减到0,第一次必然是减少中间盒子的球数
比如 1,2,3,4,5, 第一次减3 得到1,2,0,1,2 ,这时我们可以看到左右两边相等的,分冶求解
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 0;i<num;i++){
            int n = sc.nextInt();
            System.out.println(cal(n));
        }

    }

    public static int cal(int n){
        if (n==1) return 1;
        if (n==2) return 2;
        else return 1+cal(n/2);
    }


}


发表于 2020-05-20 09:31:27 回复(6)
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        //根据规律可知,即算出该十进制的二进制表示的位数
        //比如5,二进制表示为101,位数为3,则最少操作次数为3
        Scanner sc = new Scanner(System.in);
        //接收测试用例个数
        int count = sc.nextInt();
        //创建数组接收
        int[] nums = new int[count];
        //创建结果数组
        int[] ans = new int[count];
        while (sc.hasNext()){
            for (int i = 0; i <count ; i++) {
                nums[i] = sc.nextInt();
                int temp = nums[i];
                String s = Integer.toBinaryString(temp);
                ans[i] = s.length();
            }
            for (int i:ans) {
                System.out.println(i);
            }
        }
    }
}
通过所有用例。
发表于 2020-06-01 15:22:55 回复(3)
#include<bits/stdc++.h> 
using namespace std; 
int main() {
    int T;
    cin >> T;
    int n;
    while(T--) {
        cin >> n;
        cout << ceil(log2(n)) << endl;   
    }
    return 0;
}

发表于 2020-08-02 18:22:33 回复(4)
#include <iostream>

/*本题可以先理解问题的核心,选择中间值进行减少是最佳:
当N为奇数时(N=2*a+1),减少中间的值(a+1)会使得两边都变成1到a的排序
例如N=7,先取4,则得到数组[1 2 3 0 1 2 3],此时问题变成当N为3;
当N为偶数时(N=2*a),没有中间数,但减少a或者a+1的值效果一样是最优情况
例如N=6,先取3,则得到数组[1 2 0 1 2 3],此时问题同样变成当N为3
所以求N的解就是求N/2再+1,则可以求利用递归原理求解本题,即f(N)=f(N/2)+1*/

//编写递归算法
int ballNum( long int n)
{
    
    long int arr[] = { 0 };
    if (n <= 0)
    {
        return -1;
    }
    if (n == 1 )
    {
        return 1;//初始条件N=1
    }
    if (n == 2)
    {
        return 2;//初始条件N=2
    }
    else
    {
        return ballNum(n/2)+1;
    }
}

int main()
{
    int T;
    std::cin >> T;
    //注意循环从1开始
    for (int i = 1; i < T+1; i++)
    {
        long int num;
        std::cin >> num;
        std::cout << ballNum(num) << std::endl;
    }
    return 0;
}

发表于 2020-10-10 18:31:02 回复(0)
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)
笨方法:本来以为是分治,后来发现是在找规律,2、3个盒子需要2次,4、5、6、7个盒子需要3次,则n个盒子需要(logn)下取整+1次
#include<stdio.h>
#include<math.h>
#define N 100
int main(){
   int time;
   int a[N];
    int d[N];
    scanf("%d",&time);
    for(int i=0;i<time;i++){
        scanf("%d", &a[i]);
        d[i]=(log(a[i])/log(2))+1;
    }
    
    for(int j=0;j<time-1;j++){
        printf("%d\n",d[j]);
    }
    printf("%d",d[time-1]);
    return 0;
}
编辑于 2020-05-19 18:48:18 回复(5)
找规律:
N=1时,取x=1,只需要1次操作就可以使得所有盒子里没有球;
N=2时,取x=1,由1 2变为0 1,再取x=1,由0 1变为0 0,需要2次操作;
N=3时,取x=2,由1 2 3变为1 0 1,再取x=1,由1 0 1变为0 0 0,需要2次操作;
N=4时,取x=2,由1 2 3 4变为1 0 1 2,再取x=1,由1 0 1 2变为0 0 0 1,再取x=1,由0 0 0 1变为0 0 0 0,共需要3次操作;
N=5时,取x=3,由1 2 3 4 5变为1 2 0 1 2,再取x=1,由1 2 0 1 2变为0 1 0 0 1,再取x=1,由0 1 0 0 1变为0 0 0 0 0,共需要3次操作;
……
因此N个盒子,每次对球数大于等于中值的进行减少即可,共需要操作log2(N)+1次。每次盒子都被0分隔成左右两个部分,然后又可以对左右两个部分选择中值进行球的减少,也可以看作是分治过程。
import math

T = int(input())
for _ in range(T):
    N = int(input())
    print(int(math.log2(N)) + 1)


编辑于 2021-02-01 21:37:35 回复(0)
我的想法是每次折中,除0以外最大的数字加上最小的数字的和除以2,如果有余数就再加上1,这个值作为X,然后下一轮数字中最大的值势必就是(X-1)或者当前max-X
public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int T=scanner.nextInt();
        for (int i = 0; i < T; i++) {
            Long N=scanner.nextLong();
            Long min=1L;
            Long max=N;
            int count=0;
            while (max!=0)
            {
                Long X=(min+max)%2==0?(min+max)/2:(min+max)/2+1;
                max=(X-1)>(max-X)?(X-1):(max-X);
                count++;
            }
            System.out.println(count);
        }
        scanner.close();
    }
}

 
发表于 2020-08-16 19:31:59 回复(0)
#include <iostream>
#include <math.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int a;
        cin>>a;
        cout<<(int(log(a)/log(2))+1)<<endl; //每次取中点,是正方形
    }//for
    return 0;
}

发表于 2020-07-30 11:48:17 回复(0)
详细的解题思路以及代码可以参考http://39.108.236.169:8080/article/4
发表于 2020-05-26 23:57:49 回复(1)
直接算出log2(N)就好,加1是为了减去最后一个球做的操作。
import java.util.*;
public class Main {
    public static void main(String[] args){
        Main main=new Main();
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        for(int i=0;i<num;i++){
            System.out.println((int)(Math.log((double)sc.nextInt())/Math.log(2.0)+1));
        }
    } 
}
发表于 2020-12-18 16:09:42 回复(0)
import math
n=int(input())
for i in range(n):
    print(int(math.log(int(input()),2))+1)
发表于 2020-11-15 16:03:00 回复(0)






import java.util.Scanner;


public class Main 
{
    public static int find_Minium(int n )
    {
        if(n == 1)
            return 1;
        else if(n ==2)
            return 2;
        else
             return find_Minium(n/2) + 1;
        
    }
    
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for (int i = 1; i <= num; i++) 
        {
            int n = sc.nextInt();
            System.out.println(find_Minium(n));
        }
        
    }                    
}

发表于 2020-10-25 19:08:56 回复(0)
比较常规的思路吧,希望大佬指教,菜鸡秋招的苦逼解法:
case = int(input())
while case:
    tmp = int(input())
    cot =0
    if tmp=='':
        break
    def cout(tmp,cot):
        if tmp==1 or tmp==2:
            return tmp
        left = 0
        right = tmp-1
        mid = (left+(right-left))//2
        if tmp%2==1:
            cot += cout(mid,1)
        if tmp%2==0:
            cot += cout(mid+1,1)
        return cot
    res=cout(tmp, cot)+1
    print(res)
    case -=1



编辑于 2020-10-23 15:20:56 回复(0)
有没有大神帮忙看看,这个代码测试用例没问题,提示复杂度太高了,用的递归
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import static java.util.stream.Collectors.toList;

public class Main {
    public static void main(String[] args) {
        //获取输入
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        List<Integer> boxes = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            boxes.add(scanner.nextInt());
        }
        ArrayList<Integer> integers = new ArrayList<>();
        for (int i = 0; i < boxes.size(); i++) {
            integers.clear();
            for (int j = 1; j <= boxes.get(i); j++) {
                integers.add(j);
            }
            System.out.println(processBoxList(integers, 0));
        }
    }

    public static long processBoxList(List<Integer> box_list, long num) {
        int mid_idx, mid_val;
        int size_original = box_list.size();
        if (size_original == 0) {
            return 0;
        } else if (size_original == 1 || size_original == 2) {
            return size_original;
        } else {
            mid_idx = size_original / 2;
            mid_val = box_list.get(mid_idx);
            List<Integer> list_pre = box_list.stream().filter(l -> l.intValue() < mid_val).collect(toList());
            num++;
            return num + processBoxList(list_pre, 0);
        }
    }
}

发表于 2020-09-10 13:44:07 回复(0)
由大于N个球的盒子中减少N个可知,每次减少一半最合适,由此可用递归,递归一次+1,原理和求1,2,3,...,n的和相同
import java.util.Scanner;
public class Main{
    
    public static int Demo(int n){
        
          n/=2;
          if( n == 1)
              return 2;
          else
              return 1 + Demo(n);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        for(int i = 0 ;i < n ; i ++ ){
            int a = sc.nextInt();
            System.out.println(Main.Demo(a));
        }
    }
}


发表于 2020-09-08 12:04:20 回复(0)
每次写完打开评论,都觉得自己菜
def solution(t,arr):
    rs=[]
    temp=dict()
    for i in range(t):
        if arr[i] in temp:
            rs.append(temp[arr[i]])
            continue
        n=arr[i]
        count=0
        while n>0:
            n=int(n/2)
            count+=1
        temp[arr[i]]=count
        rs.append(count)
    for i in range(t):
        print(rs[i])
if __name__=='__main__':
    t=int(input())
    arr=[]
    for i in range(t):
        arr.append(int(input()))
    solution(t,arr)
发表于 2020-09-07 17:30:32 回复(0)
importjava.util.*;
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner sc = newScanner(System.in);
        intT = sc.nextInt();
         //每次都是取中间,所以就是一分为2。因此不断的除以2,并记录除以2的次数,即为结果
        for(inti = 0; i < T; i++){
            intN = sc.nextInt(); //输入魔盒的个数N
            intnums = 0;
            while(N > 0){
                N /= 2;
                nums++;
            }
             
            System.out.println(nums);
        }
    }
}
发表于 2020-09-01 16:22:44 回复(0)
之前做的时候只是凭感觉加举例子发现应该是每次都选择中间的数往后减,今天突然想到了证明方法。
设第一次选择第 i 个盒子往后减,则能拿掉的球数量为    i*(N-i+1)   。为了使总次数最少,每次拿球的数量应该尽可能多。对于这个式子来说,当   i=N-i+1   即    i=(N+1)/2    时,值最大。也就是所谓的中间盒子。第一次拿球完成后,序列将变成相同的两半或者后半部分多一个数,
1,2,...,0.5N-1,0,1,2,...,0.5N。
然后再递归的对每一半再选择中间盒子往后拿球就好了。保证了每次都拿球数最多。
发表于 2020-08-28 10:15:04 回复(0)