[编程题]贪吃的小Q

[编程题]贪吃的小Q

题目：小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力
思路：

1. 穷举法
   第一天吃M块能否满足要求，不满足则判断
   第一天吃M-1块能否满足要求，不满足则判断
   第一天吃M-2块能否满足要求，不满足则判断
   ......
   直到找到第一天吃M-x块满足要求，则M-x是他第一天最多能吃的巧克力

2. 二分查找法
   如果M-x块能满足题目要求，且第一天吃M-x+1块不满足要求,则M-x块是他第一天最多能吃的巧克力
   如果M-x块不能满足题目要求，且第一天吃M-x-1块满足要求，则M-x-1块是他第一天最多能吃的巧克力

   import java.util.Scanner;
   public class Main {
     private static int n;//出差n天
     private static int m;//m块巧克力
     public static void main(String[] args) {
         Scanner in = new Scanner(System.in);
         n = in.nextInt();
         m = in.nextInt();
         in.close();
         int min = 0, max = m;
         int mid=0;
         while (min < max) {
             mid = (min + max) / 2;
             if (help(mid)) {
                 if (!help(mid + 1)) {//第一天最多能吃mid块
                     break;
                 } else {
                     //输入n=1，m=12345程序运行到==》mid=12344,min=12344,max=12345，min=mid+1后就会跳出循环，但是mid并不符合要求
                     //如果不跳出循环，则mid随后也会被更新
                     min = ++mid;
                 }
             } else {
                 if (help(mid - 1)) {//第一天最多能吃mid-1块
                     mid--;
                     break;
                 } else{
                     max = mid - 1;
                 }
             }
         }
         System.out.println(mid);
     }
   
     /**
      * 判断第一天吃x块能否满足题目要求
      *
      * @param x 第一天吃x块
      * @return
      */
     public static boolean help(int x) {
         int tmp=m;//定义局部变量来替代m，不能在循环的时候改变m
         for (int i = 1; i <= n; i++) {
             if (x <= tmp) {
                 tmp -= x;
                 x = (x + 1) / 2;//如果x是偶数，则x/2=(x+1)/2;如果x是奇数，则第二天应该吃x/2+1=(x+1)/2
             } else {
                 return false;
             }
         }
         return true;
     }
   }