[编程题]贪吃的小Q

热度指数：13094 时间限制：1秒空间限制：32768K
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

3 7

输出

算法知识视频讲解

C/C++

小冲冲

#include<iostream>
using namespace std;
int n,m;
//计算第一天吃s个巧克力一共需要多少个多少个巧克力
int sum(int s){
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=s;
        s=(s+1)>>1;//向上取整
    }
    return sum;
}
//二分查找
int fun(){
    if(n==1) return m;
    int low=1;
    int high=m;//第一天的巧克力一定是大于等于1小于等于m的
    while(low<high){
        int mid=(low+high+1)>>1;//向上取整
        if(sum(mid)==m) return mid;//如果第一天吃mid个巧克力，刚刚好吃完所有巧克力，那么直接返回
        else if(sum(mid)<m){
            low=mid;
        }else{
            high=mid-1;
        }
    }
    return high;
}
int main()
{
    cin>>n>>m;
    int res=fun();
    cout<<res<<endl;
    return 0;
}

发表于 2018-07-03 20:54:50 回复(20)

GYshadows

二分查找法：修改了一下大佬的边界条件

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int day = scan.nextInt();
        int number = scan.nextInt();
        System.out.print(fun(day,number));
    }

    //计算第一天吃s个巧克力一共需要多少个多少个巧克力
    public static int sum(int s, int n, int m){
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=s;
            s=(s + 1)/2;//向上取整
        }
        return sum;
    }
    //二分查找
    public static int fun(int n, int m){
        if(n==1) return m;
        int low=1;
        int high=m;//第一天的巧克力一定是大于等于1小于等于m的
        while(low<=high){
            int mid=(low+high + 1)/2;//向上取整
            if(sum(mid, n, m)==m) return mid;//如果第一天吃mid个巧克力，刚刚好吃完所有巧克力，那么直接返回
            else if(sum(mid, n, m)<m){
                low=mid+1;
            }else{
                high=mid-1;
            }
        }
        return high;
    }
}

发表于 2018-08-04 11:01:24 回复(3)

算法才是灵魂

二分查找求第一天可能吃的最多糖数

n,m = map(int, input().split())

def countSuger(num, k):
    res = 0
    while k > 0:
        res += num
        num = num // 2 + num % 2
        k -= 1
    return res

left , right = 0, 100000
while left < right:
    mid = (left + right) // 2 + 1
    if countSuger(mid, n) <= m:
        left = mid
    else:
        right = mid - 1
print(left)

发表于 2019-08-10 16:43:35 回复(2)

看我脸上有啥

一开始我也是按穷举，判断当第一天吃所有的巧克力是否满足，如果不满足巧克力减1判断是否满足，这样继续减2减3减4.。。。。。。直到减到某个数满足题意即是最大的第一天吃的巧克力数，但是结果超时只能过80%。

那么问题就在于从最大的一个一个往前找速度太慢了，时间复杂度高，就可以改为二分查找：

首先赋低位min为0，高位max为所有巧克力数n，

while(min<max),循环试探（min+max）/2向上取整个数个巧克力是否满足题意，

1：如果满足题意，那么再判断一下（min+max）/2向上取整+1个数个巧克力是否满足题意：

（1）如果不满足题意，那么就说明当前的（min+max）/2向上取整个巧克力就是要找的最大的

（2）如果满足题意，那么就说明当前的（min+max）/2向上取整个巧克力取小了，赋低位min=（m in+max）/2向上取整，继续while循环试探

2：如果不满足题意，那么说明当前的（min+max）/2向上取整个巧克力取大了，赋高位max=（min+max）/2向上取整，继续while循环试探

经二分查找改造后，满分~

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

     public static void main(String[] args) {
    
         Scanner sc=new Scanner(System.in);
         int n=sc.nextInt();//天数
         int m=sc.nextInt();//巧克力个数
         double min=0;//设置二分初始低位为0
         double max=(double)m;//设置二分初始高位为初始巧克力个数m
         double stillHas=(double)m;//剩余巧克力个数
         boolean flag=true;
         double temp;
         while(min<max)//当低位<高位时，开始二分查找
         {
             temp=Math.ceil((min+max)/2);//取低位和高位中间的一位向上取整，即为试探的第一天吃的巧克力数
             for(int i=1;i<n+1;i++)//循环n天
             {
                 if(temp<=stillHas)//当前天需要吃的巧克力个数<=剩余巧克力个数时，减少巧克力，同时第二天巧克力个数变为第一天的一半
                 {
                     stillHas=stillHas-temp;
                     temp=Math.ceil(temp/2);
                    
                 }
                 else//当前天需要吃的巧克力个数>剩余巧克力个数时,说明没有撑到n天巧克力吃完，置flag=false;跳出循环
                 {
                     flag=false;
                     break;
                 }
             }
             if(flag)//flag==true，说明上面的for循环正常循环结束跳出，说明当前的第一天吃的Math.ceil((min+max)/2)个巧克力满足要求
             {
                //判断一下，如果比Math.ceil((min+max)/2)个巧克力大1个巧克力时
                //isTrue返回false说明再大1个巧克力就不满足要求了，那么当前的Math.ceil((min+max)/2)就是最大的第一天吃的巧克力数，输出即可
                 if(!isTrue(n,m,Math.ceil((min+max)/2)+1)) 
                 {
                     System.out.println((int)Math.ceil((min+max)/2));
                     return;
                 }
                 //如果大1个巧克力仍然满足要求那么说明当前的第一天吃的Math.ceil((min+max)/2)取小了应取大一点的巧克力数，需要继续二分查找
                 else
                 {
                     min=Math.ceil((min+max)/2);//取低位为当前的试探的第一天吃的巧克力数
                     stillHas=(double)m;//重置剩余巧克力数为总数
                 }
                
             }
            //flag==false，说明上面的for循环遇到break跳出，说明当前的第一天吃的Math.ceil((min+max)/2)取大了应取小一点的巧克力数，需要继续二分查找
             else
             {
                 max=Math.ceil((min+max)/2);//取高位为当前的试探的第一天吃的巧克力数
                 stillHas=(double)m;//重置剩余巧克力数为总数
                 flag=true;//重置标志位
             }
             
         }
         
     }
     //用于判断当每天吃X个巧克力时是否能撑到父母回来的静态方法
     public static boolean isTrue(int n,double m,double x)
     {
         for(int i=1;i<n+1;i++)
         {
             if(x<=m)
             {
                 m=m-x;
                 x=Math.ceil(x/2);
                
             }
             else
             {
                 return false;
             }
         }
         return true; 
     }
}

发表于 2019-03-30 23:17:20 回复(0)

一位匿名网友

在域外創音大佬的基础上做了一点修改：

#include<iostream>
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;} //初始分配：每天最少吃1块
    int alignable = m-n;
    int result = 1; //如果可以某种power2[i]-1的方式分配，便进入。具体的分配是：第一天多吃power2[i-1]块，第二天多吃power2[i-2]块，依此类推。
    //这样一来，只要每个追加分配所对应的i不重复，每天吃的块数就依然能符合要求，因为第j天吃的块数最多等于power2[从i-j到0]+1，一定大于power2[从i-j-1到0]的二倍。
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
        {
            if(i>0)//防止越界
                result+=power2[i-1];
            int assigned = 0;
            if(i>n)
                assigned = (power2[i]-1) - (power2[i-n]-1);
            else
                assigned = (power2[i]-1);
            alignable -= assigned;
        }
    std::cout<<result<<std::endl;
    return 0;
}

原代码找到一个测试用例存在问题：（3天，20块），可以得到按照（11，6，3）分配为最优解，而原代码得出结果10；可以找到问题出在原代码18行，当天数n小于i时，原代码的已分配数量过多。

另外17行的i-1，在下愚钝认为有可能越界，加上了判别条件（但是使用牛客的OJ并没有发现会真的越界导致出错）。

代码的具体思路发在http://makdon.me/2019/03/04/%E7%BC%96%E7%A8%8B%E9%A2%98%E8%B4%AA%E5%90%83%E7%9A%84%E5%B0%8Fq-%E7%AE%97%E6%B3%95%E9%A2%98%E8%AE%B0%E5%BD%95/

发表于 2019-03-05 09:38:40 回复(0)

域外創音

#include 
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;}
    //初始分配：每天最少吃1块
    int alignable = m-n;
    int result = 1;
    //如果可以某种power2[i]-1的方式分配，便进入。具体的分配是：第一天多吃power2[i-1]块，第二天多吃power2[i-2]块，依此类推。
    //这样一来，只要每个追加分配所对应的i不重复，每天吃的块数就依然能符合要求，因为第j天吃的块数最多等于power2[从i-j到0]+1，一定大于power2[从i-j-1到0]的二倍。
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
    {
        result+=power2[i-1];
        alignable -= (power2[i]-1);
    }
    std::cout<<result<<std::endl;
    return 0;
}

可以从分配的角度来看，这样的算法可以把时间复杂度和空间复杂都减少到O(log(m))

编辑于 2018-09-15 18:28:06 回复(1)

infiniteft

import math
def calc_total_chocolate(first_day_chocolate, days):
    total_chocolate = 0
    chocolate_of_day = first_day_chocolate
    for i in range(days):
        total_chocolate += chocolate_of_day
        chocolate_of_day = (chocolate_of_day + 1) >> 1
        # 当某一天吃的巧克力等于1时，之后每一天吃的巧克力都为1，可以直接计算出之后每一天吃的总的巧克力
        if chocolate_of_day == 1:
            total_chocolate += days - i - 1
            break
    return total_chocolate
 
def find_first_day_max_chocolate(m, n):
    # 通过等比数列计算求和公式得到第一天吃的巧克力的最大下限
    # 也就是说，真的每一天吃的巧克力数要大于这个下限
    first_day_chocolate = 1 + math.ceil((m - n + 1) / 2)
    while 1:
        total_chocolate = calc_total_chocolate(first_day_chocolate, n)
        if total_chocolate > m:
            first_day_chocolate -= 1
            break
        elif total_chocolate < m:
            first_day_chocolate +=1
        else:
            break
    return first_day_chocolate
 
if __name__ == '__main__':
    n, m = map(int, input().strip().split())
    print(find_first_day_max_chocolate(m, n))

编辑于 2019-10-21 00:24:33 回复(0)

Python

BobLeeR

找到前面几天最快到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)

stupid-boy

n,m = map(int, input().split(" "))
 
def SumEat(e1,N):
    S = 0
    e = e1
    for i in range(0,N):
        S += e
        e = (e+1)//2
    return S
 
def BinarySearch(N,M):
    if N == 1:
        return M
    low = 1
    high = M
    while low<high:
        mid  = (low+high+1)//2
        if SumEat(mid,N)<=M:
            low = mid 
        else:
            high = mid -1
    return low
 
print(BinarySearch(n,m))

发表于 2019-09-01 12:29:26 回复(0)

改个名字没人认识我

import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int[] array= new int [n];
int M=sc.nextInt();
M=M-n;
for(int i=0;i<n;i++)
array[i]=1;
while(--M>=0)
{ array[0]++;
for(int i=0;i<n-1;i++)
{
if(2*array[i+1]<array[i])
{
array[i]--;
array[i+1]++;
}
if(array[i+1]==1&& array[i]==1)
break;
}
}
System.out.println(array[0]);
// System.out.println(Arrays.toString(array));
}

}

发表于 2019-06-12 15:59:12 回复(1)

秋心拆两半

//二分查找，修改大佬们的边界，直接返回大于目标值的第一个下标  
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(process(n, m));
    }

    public static int process(int n, int m){
        int l = 1;
        int r = m;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(sum(mid, n) > m){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l - 1;
    }

    public static int sum(int s, int n){
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += s;
            s = (s + 1) / 2;
        }
        return sum;
    }
}

发表于 2019-04-17 21:04:35 回复(0)

皮尔超

import sys

s = list(sys.stdin.readline().split(' '))
n = int(s[0])

m = int(s[1])

def sum(first, day):
count = 0
for i in range(day):
count = count+ first
first = int((first + 1)/2)
if first == 0:
first = 1

    return count

def fun(x, y):
if x==1:
return y
low = 1
high = y
while low <= high:
mid = int((low + high + 1)/2)
if sum(mid, x) == y:
return mid
elif sum(mid, x) < y:
low = mid + 1
else:
high = mid - 1

return high

print(fun(n, m))

发表于 2019-03-18 15:35:19 回复(0)

华尔

#include <iostream>
using namespace std;
 
void back_order(int& count, int& idx, int max_idx, int depth, int max_depth) {
    if (idx>max_idx) {
        return;
    }
    if (depth == max_depth) {
        count++;
        return;
    }
    else {
        idx++;
        back_order(count, idx, max_idx, depth + 1, max_depth);
        idx++;
        back_order(count, idx, max_idx, depth + 1, max_depth);
    }
 
}
 
int main() {
    int days, foods;
    while (cin >> days >> foods) {
        int res = 0;
        if (days <= 31) { //考虑树直接满了的情况
            int full_foods = (1 << days) - 1;
            int full_tree = foods / full_foods;
            res += full_tree * (1 << (days - 1));
            foods = foods % full_foods;
        }
        int idx = 1;
        back_order(res, idx, foods, 1, days);
        cout << res << endl;
    }
    return 0;
}

二叉树遍历解决问题

编辑于 2019-03-09 10:31:35 回复(0)

heimingsheng

list = input().split()
N = int(list[0])
Q = int(list[1])
day1_eat = Q
#从一半开始判断
max_eat = Q
while day1_eat >= 0:
days = N
eat = 0
every_day_eat = day1_eat
while days > 0:
eat += every_day_eat
every_day_eat = int(every_day_eat/2) if every_day_eat % 2 == 0 else int(every_day_eat/2) + 1
days -= 1
if every_day_eat == 1:
eat += days
break

#从大到小第一个满足要求的即可
if eat <= Q:
max_eat = day1_eat
break
day1_eat -= 1
print(max_eat)

发表于 2019-03-08 11:45:06 回复(0)

老谋

#include<iostream>
using namespace std;

//a^p
int pow(int a,int p)
{
    if(p==0) return 1;
    int re=1;
    while(p!=0)
    {
        if(p&1==1) re*=a;
        a*=a;
        p>>=1;
    }
    return re;
}
/*主要解法为求出result的可能的最小值及最大值，再从中遍历，其中利用等比数列的公式*/
/*在巧克力不足的情况下（最后几天会只吃一块）
 *最大值对应数列为1,2,4,8,16...
 *最小值对应数列为2,3,5,9,17...
 */
int main()
{
    int n,m;
    cin>>n>>m;
    int base=m-n+1;
    int i,j,k,max,min;
    if(n<30&&(int)(m/(pow(2,n)-1.0)+0.5)>1)    //巧克力充足
    {
        max=(int)(m/(pow(2,n)-1.0)+0.5);
        min=(int)(m/(pow(2,n)-1.0));
    }
    else    //巧克力不足
    {
        for(i=0;pow(2,i)-i<=base;i++);
        max=pow(2,i-1);
        for(i=0;pow(2,i)<=base;i++);
        min=pow(2,i-2)+1;
    }
    int sum=0;
    for(i=min;i<=max;i++)
    {
        sum=0;
        k=i;
        for(j=0;j<n;j++)
        {
            sum+=k;
            k=(k+1)>>1;
        }
        if(sum>m) break;
    }
    cout<<i-1<<endl;
    return 0;
}

发表于 2018-08-20 14:25:27 回复(0)

(≧∇≦)三玖

n, m = tuple(map(int,input().split()))
def less_suger(s,n):
    less = 0
    for i in range(n):
        less += s
        s = s//2+s%2  # 向上取整
    return less
left,right = 0, m
while True:
    if n == 1:
        print(m)
        break
    s=(left+right)//2
    res = less_suger(s,n)
    if res==m:  
        print(s)
        break
    elif res>m:
        right = s
    else:
        left = s
    if right - left == 1:
        print(left)
        break

发表于 2019-09-24 19:11:27 回复(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 回复(0)

Unitl

我们不考虑复杂的边界问题，只是在普通的二分查找基础上稍作修改也可以通过。

#include<iostream>
using namespace std;
int sum(int n,int count)
{
    int sum1 = 0;
    for (int i = 0; i < n; i++)
    {
        sum1 += count;
        count = (count + 1) >> 1;
    }
    return sum1;
}
int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        if (n == 1)
        {
            cout << m << endl;
            continue;
        }
        int flag = 0;
        int low = 1, high = m;
        int mid;
         
        while (low <= high)
        {
             
            mid = (low + high + 1) >> 1;
            if (sum(n, mid) > m)//遇到比m大的high往前走，
            {
                high = mid - 1;
            }
            else//如果相等或者小于，就继续往后走，直到退出循环，也就是说high停留的位置始终是最后一个符合的mid
            {
                low=mid+1;
            }
        }
        if(high>=1&&sum(n,high)<=m)
        //退出循环后，说明
        cout << high << endl;
    }
    system("pause");
    return 0;
}

发表于 2019-09-09 22:03:46 回复(0)

C/C++

银叶

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    int n, M, sum, val, i;
    cin >> n >> M;
    sum = M;
    for(i = n; i > 0; i--)
    {
        val = (sum - 1) / (pow(2, i) - 1) + 1;
        sum -= val;
    }
    cout << val << endl;
    return 0;
}

思路：按照吃的数量加倍的方法，找到最后一天吃的最小数目，然后减去这一天的数目。将剩余的问题化作n-1天情况下的同类问题，循环n次即可找到第一天吃的数目。（可以证明，这样计算每一天吃的数目不超过下一天的两倍）

编辑于 2019-09-05 10:48:16 回复(0)