18935 貪吃的小Q
Description
騰訊2018春招技術(shù)類編程題

小Q的父母要出差N天，走之前給小Q留下了M塊巧克力。
小Q決定每天吃的巧克力數(shù)量不少于前一天吃的一半，但是他又不想在父母回來之前的某一天沒有巧克力吃，
請(qǐng)問他第一天最多能吃多少塊巧克力？

輸入格式
一行包含兩個(gè)正整數(shù)，表示父母出差的天數(shù)N(N<=50000)和巧克力的數(shù)量M(N<=M<=100000)

輸出格式
輸出一個(gè)數(shù)表示小Q第一天最多能吃多少塊巧克力。

輸入樣例
3 7

輸出樣例
4

思路：
因?yàn)槭遣荒茉谀骋惶鞗]有得吃，所以設(shè)邊界為最后一天剩一塊，利用二分查找從 1 到 M 中查找第一天吃的巧克力數(shù)，求得按照要求的最低的標(biāo)準(zhǔn)（不少于前一天的一半，即按一半），由于巧克力數(shù)必須為整數(shù)，因此向上取整。
利用二分查找法查找邊界
PS：注意取整、邊界處

#include <iostream> #include <cstdio> #include <stdlib.h>using namespace std;int N,M;int Eat(int x){//第一天吃x塊，推到巧克力總數(shù)int sum = 0;for(int i = 1;i <= N;i++){ //注意是N天sum += x;//后一天吃的（不少于一半，所以向上取整）x = (x + 1) / 2;}//第N天,得到第一天吃s塊情況下的巧克力總數(shù)return sum; }int Choco(){//二分法if(N == 1) return M;int low = 1,high = M,mid;//low = 1是最后一天至少剩一塊while(low <= high){ //注意邊界//mid要在循環(huán)內(nèi)計(jì)算mid = low + (high - low) / 2;//注意邊界，這里如果和是奇數(shù)會(huì)向下取整（后面要+上）if(Eat(mid) == M) return mid;else if(Eat(mid) > M) high = mid - 1;//太多了了，要找比mid更小的else low = mid + 1;//這里加1補(bǔ)上邊界}return high;//返回找到的最多塊數(shù) }int main() {scanf("%d%d",&N,&M);int res = Choco();printf("%d\n",res);return 0; }

參考：貪吃的小Q

總結(jié)

以上是生活随笔為你收集整理的18935 贪吃的小Q的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。