教育改变生活

标题: 拼多多面试真题-多多的魔术盒子 [打印本页]

作者: 一秉 时间: 2020-7-3 20:32
标题: 拼多多面试真题-多多的魔术盒子
题目描述
多多鸡有N个魔术盒子（编号1～N），其中编号为i的盒子里有i个球。
多多鸡让皮皮虾每次选择一个数字X（1 <= X <= N），多多鸡就会把球数量大于等于X个的盒子里的球减少X个。
通过观察，皮皮虾已经掌握了其中的奥秘，并且发现只要通过一定的操作顺序，可以用最少的次数将所有盒子里的球变没。
那么请问聪明的你，是否已经知道了应该如何操作呢？
实现思路：
要用最少的次数把所有盒子减到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);
}

}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)