腾讯，贪吃的小Q

怼烎@ 2022-03-29 14:30 358阅读 0赞

**题目描述**  
小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

## 思路 ##

需要注意的是，每天吃的巧克力的数目不少于前一天吃的一半，但是每天吃的巧克力的数目>=1，因此可以算得第一天吃巧克力个数最多为m - (n - 1)。  
如果从这个值开始遍历恐怕会超时，因此采用二分法  
除以2可以改成>>1，从而加快代码的效率

从数组中找出一个满足要求的数字，可以优先考虑二分法

--------------------

## 代码 ##

n, m = map(int, input().split())
    max = m - (n - 1)  #第一天吃最多巧克力的个数
    def EatNum(firstNum):
        sum = 0
        for i in range(n):
            sum += firstNum
            j = int(firstNum >> 1)
            while j << 1 < firstNum:    #不少于前一天的一半，并且需要是整数
                j += 1
            firstNum = j
            if firstNum < 1:
                firstNum = 1
        return sum
    def MaxEat():
        low, high = 0, max
        while low <= high:
            mid = (low + high) >> 1
            if EatNum(mid) <= m and EatNum(mid + 1) > m:
                return mid
            if EatNum(mid) <= m:
                low  = mid + 1
            else:
                high = mid - 1
    print(MaxEat())

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220329/d8bbfc21be874bbc91e3b1dea20f94de.png