騰訊----貪吃的小Q

文章目錄

• • 騰訊----貪吃的小Q
  • 一、題目描述
  • 二、分析
  • 三、代碼

一、題目描述

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

輸入描述:

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

輸出描述:

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

輸入例子1:

3 7

輸出例子1:

4

二、分析

• 首先我們可能會(huì)想到從最后一天吃的巧克力的數(shù)量來往前反推第一天吃巧克力的數(shù)量，但是我們并沒有一個(gè)合適的值來進(jìn)行反推，所以直接pass掉

• 那么我們就只能在第一天下手，我們就 枚舉第一天所有可能吃掉的巧克力的數(shù)量，然后根據(jù)每個(gè)數(shù)量計(jì)算N天一共吃掉的巧克力的數(shù)量和M塊巧克力的數(shù)量進(jìn)行比較。

• 如果從[1....M]逐個(gè)進(jìn)行枚舉，那么肯定是可以的，但是效率比較低，那么什么方法適合這種枚舉的場景呢----->二分查找二分查找詳解

• 舉例：

n=3 m=7我們有七塊巧克力1 2 3 4 5 6 7首先我們找到中間位置的巧克力個(gè)數(shù)(向上取整，因?yàn)闆]有3.5個(gè)巧克力)(1+7+1)/2=4就是4位置的巧克力然后我們以它作為第一天的起始巧克力個(gè)數(shù)對這些天所需要的總巧克力個(gè)數(shù)進(jìn)行求和， 最終的結(jié)果總巧克力數(shù)目如果等于m那么直接返回4，如果小于m，那么可能存在 更優(yōu)的解在[5,7]區(qū)間內(nèi)，那么需要在5位置到7位置中間位置繼續(xù)做相同的操作。如果大于m，那么證明我們第一天給的巧克力的數(shù)目太多了，需要在[1-3]區(qū)間內(nèi)繼續(xù)找合適的解。

三、代碼

#include<iostream> using namespace std;//n代表天數(shù)，m代表巧克力的數(shù)量 int n, m;//函數(shù)用來求第一天吃mid塊巧克力，根據(jù)題意N天共吃掉巧克力的數(shù)量 int sum(int &mid) {int tmp = mid;int total = tmp;for (int i = 0; i < n -1; ++i){tmp = (tmp + 1) / 2;total += tmp;}return total; }int fun() {int l = 1;int r = m;while (l <= r){int mid = (l + r + 1) / 2;int bool_int = sum(mid);if (bool_int == m){return mid;}else if (bool_int < m){l = mid + 1;}else{r = mid - 1;}}return r;} int main() {cin >> n >> m;cout << fun() << endl;return 0; }

總結(jié)

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

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