贪吃的小Q

算法week1

题目：
链接：https://www.nowcoder.com/questionTerminal/d732267e73ce4918b61d9e3d0ddd9182?orderByHotValue=1&page=1&onlyReference=false
来源：牛客网

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

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。

输出描述:

输出一个数表示小Q第一天最多能吃多少块巧克力。

示例1

输入
3 7
输出
4

//后一天要比前一天多，或者相等
//二分查找从1到M查找第一天吃的巧克力数，求得按照要求的最低的标准（不少于前一天的一半）
//暴力循环
//（N<=50000） (N<=M<=100000)
#include <iostream>
using namespace std;
int sum(int s,int day)
{
    int sum=0;
    for(int i=0; i<day; i++)
    {
        sum+=s;
        s=(s+1)/2;
    }
    return sum;
}
int SearchMax(int total, int day)
{
    int low = 1;
    int high = total;
    if(total == day)
        return 1;
    if(day == 1)
        return total;
    while(low < high)
    {
        int mid = (low+high+1)/2; //(low+high)/2为什么不行？
        if(sum(mid,day) == total)
            return mid;
        else if(sum(mid,day) <total )
            low = mid;
        else
            high = mid-1;
    }
    return high;
}
int main()
{
    int M,N;
    cin>>N>>M;
    int one = SearchMax(M,N);
    cout<<one<<endl;
    return 0;
}

注意二分法的边界控制