贪吃的小Q

[编程题]贪吃的小Q

热度指数：20629 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

3 7

输出

算法知识视频讲解

Python

必有offer

n,m = map(int, input().split(" "))
def SumEat(e1,N):
    #计算N天一共吃了多少巧克力
    S = 0
    e = e1
    for i in range(0,N):
        S += e
        e = (e+1)//2
    return S
 
def BinarySearch(N,M):
    #二分查找的变异，应用
    #创建[1,2,3,...,m]
    #以二分查找的方式，判断该位置的元素是不是满足第一天，调用SumEat函数
    if N == 1:
        return M
    low = 1
    high = M
    while low<high:
        mid  = (low+high+1)//2
        #满足就是mid
        if SumEat(mid,N)<=M:
            low = mid 
        else:#不满足的话就用mid前面的元素
            high = mid -1
    return low 
print(BinarySearch(n,m))

发表于 2020-09-03 15:31:01 回复(0)

Python

0b100001101000

找到前面几天最快到1的步骤，剩下的用1补齐：

n,m = map(int, input().split())
if n == 1:
    print(m)
    exit()
for i in range(m-n+1,1,-1):
    t = i
    s = 0
    r = 0
    while t!=1:
        s += t
        r += 1
        t = (t+1)//2
    if m-s >= n-r:
        print(i)
        break

148 ms

3440K

Python 3

发表于 2019-09-24 22:42:59 回复(0)

Python

Mia_Ye

二分法查找。

许愿腾讯 🎋

晚点来写 comment～～

import sys
n, m = map(int, sys.stdin.readline().strip().split(' '))
 
def countchoc(n,l):
    count=0
    j=l
    for _ in range(n):
        count += j
        j = j//2 +j%2
    return count

def solution1(n,m):
    if m==n:
        return 1
    left,right = 1, m-n+1
    mid = (left+right)//2
    if countchoc(n,right) == m:
        return right
    while right-left>1:
        if countchoc(n,mid) == m:
            return mid
        elif countchoc(n,mid) > m:
            right = mid
            mid = (left+right)//2
        elif countchoc(n,mid) < m:
            left = mid
            mid = (left+right)//2
    return mid

print(solution1(n,m))

发表于 2019-09-20 19:52:03 回复(1)

Python

鼠标点点点点

其实是一个等比数列求和问题：通过叠加求和，在叠加求和的过程中对为2的那一天判断（降低复杂度），2之后的每天都是吃一块，放一个python的答案吧，代码的复杂度较高，通过率仅70%，还需要优化一下；

import math
import sys

data = sys.stdin.readline().strip().split()
day = int(data[0])
eat = int(data[1])

for i in range(1,eat):
count = 0
for j in range(1,day+1):
if math.ceil(i *((0.5)**(j-1)))<2:
count = count + day - j +1
break
else:
count = count + math.ceil(i *((0.5)**(j-1)))

if count> eat:
print(i-1)
break

else:
continue

发表于 2018-07-22 11:20:18 回复(1)