欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

腾讯2018秋招笔试题之贪吃的小Q

程序员文章站 2022-06-09 11:08:47
...

小Q的父母要出差N天,走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半,但是他又不想在父母回来之前的某一天没有巧克力吃,请问他第一天最多能吃多少块巧克力。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数,表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。

输出描述:
输出一个数表示小Q第一天最多能吃多少块巧克力。
示例1
输入
3 7
输出
4

知识点:二分

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,temp,now,mid;
    bool flag;
    scanf("%d%d",&n,&m);
    int l=1,r=m;
    while(l!=r)
    {
        flag=true;
        mid=(l+r+1)/2;
        temp=m;
        now=mid;
        for(int j=0; j<n; j++)
        {
            if(temp<now)
            {
                flag=false;
                break;
            }
            temp-=now;
            now=(now+1)/2;
        }
        if(flag)
            l=mid;
        else
            r=mid-1;
    }
    printf("%d\n",l);
    return 0;
}