果冻豆---算法详细解析

末蓝、 2023-07-03 12:06 8阅读 0赞

**题目描述**

安卓4.1版本的代号叫果冻豆（Jelly Bean），当时发布的时候，小明就对这个果冻豆很好奇，因为他以前没有吃过果冻豆，于是他去买了一盒果冻豆，当他吃下第一颗果冻豆的时候，他爱上了果冻豆。

之后小明又买了好多果冻豆，小明把它们放到n个盒子里，在第i个盒子里有i个果冻豆（i=1,2,3,…,n）。小明每天选择一个整数x，再选择一些 装着果冻豆的盒子，这些被选中的盒子每个盒子里的果冻豆数量至少为x，然后小明吃掉每个被选中的盒子里的x个果冻豆。小明想尽快吃完所有的果冻豆，越快越 好，所以想请你计算一下小明最快需要几天可以吃完所有的果冻豆？

输入

输入包含多组测试数据。

输入的第一行是一个整数T，表示有T组测试数据。

每组输入一个正整数n，n的含义见题目描述，n在int范围内。

输出

对于每组输入，输出所要求的结果。

样例输入 Copy

4  
1  
2  
3  
4  
样例输出 Copy

1  
2  
2  
3

java版本

package x;
     
    import java.util.Scanner;
     
    public class Main { 
    	
    		public static void main(String[] args) { 
    			Scanner sc =  new Scanner(System.in);
    		  int T = sc.nextInt(); 
    		  for(int i=0;i<T;++i) 
    		  { 
    			  int n = sc.nextInt(); 
    			  System.out.println(eat(n));
    	      }
    		 
    			//System.out.println(eat(6));
    		}
    		public static int eat(int n) { 		
    				if(n<=1)
    					return 1;
    				else if(n==2)
    					return 2;
    				return 1+eat(n/2);
    		
    		}
    }

c++ 版本解法

#include<iostream>
    #include<cmath>
    using namespace std;
    int main()
    { 
    	int n,t;
    	cin >> t;
    	while (t--)
    	{ 
    		cin >> n;
    		for (int i = 1; i <= n; i++)
    		{ 
    			if (n >=pow(2,i-1) && n <pow(2,i)) 
    			 {  cout << i << endl; break;}
    		}
    	}
    }

大概思路：  
这个题就是个找规律的题；题目看完了确实有点高大上；但是  
你品，细品！  
n是盒子数

1个盒子最快吃完是1天  
2个盒子不管怎么吃 都是2天  
3个盒子最快也是 2天（例：第一天吃两个）  
4个盒子最快 是 3 天

**从而发现规律 ：天数是 2的次方数 ，而盒子数不超过 此 2的天数的次方！  
例如3< 2 ’ (2) 4= 2 ’ (2)**

而java版本解法 也是大致思路 但是不是次方数的规律  
而是倍数之间的关系  
都是纯规律性质的写法

## 一起进步！！！ ##