首页 > 试题广场 >

贪吃的小Q

[编程题]贪吃的小Q
  • 热度指数:20519 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小Q的父母要出差N天,走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半,但是他又不想在父母回来之前的某一天没有巧克力吃,请问他第一天最多能吃多少块巧克力

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


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

输入

3 7

输出

4
一开始我也是按穷举,判断当第一天吃所有的巧克力是否满足,如果不满足巧克力减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 回复(1)

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

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)
二分查找法:修改了一下大佬的边界条件

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)

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)

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

#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)
1)得先保证后面每天都有巧克力吃,每天基础值为1。如果有多的,再逐步提高第一天
的门槛。用一个双端有界队列实现。
2)为了让更多巧克力集中在第一天,应该用最少的天数快速将巧克力数量提升到最大
(最大是我的目标,因为每天不能少于前一天的一半,我得慢慢铺垫这个最大值,但是
铺垫不能占用我太多巧克力),因此等比q就是2。
3)有多的就往第一天加。因为每天不能少于前一天的一半,给第一天加1可能引起后面
多天级联加1,这种级联就和加法进位一样,只不过是加两次才进。可以用boolean标记,
而且,每加1就需要一块巧克力。如果给第一天加巧克力不足以支持整个级联关系需要
的巧克力,那这一趟就不能加了,刚刚第一天的数就已经是最大的了。
import java.util.LinkedList; import java.util.Scanner; public class Main {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         int d = in.nextInt();         int m = in.nextInt();         LinkedList<Integer> q = new LinkedList<>();     //做有界队列         for(int i = d;i>0;i--){     //先将队列填满1,保证每天都有得吃             q.add(1);             m--;         }         //假如可以“滚动队列”,即去掉队尾最小的元素,然后在对头添加一个更大的,那就这么干。         while(true){             int t = q.peek();             if( m+q.peekLast() >= t*2 ){                 m += q.pollLast();                 q.addFirst(t*2 );                 m -= t*2 ;             }else break;         }         //巧克力恰好耗尽,不需要继续了         if(m==0){             System.out.println(q.peek());             return;         }         // 把剩余不够凑成一个更大的值的数巧克力分散到已经有的数中         boolean[] full = new boolean[d];         //LinkedList 数据转数组,方便获取下一个元素         int[] base = new int[d];         for(int i = 0;i<d;i++){             base[i] = q.poll();             if(base[i]>1)                 full[i] = true;             else                 full[i] = false;         }         while(m>0){             int i = 0;             while (i<d){                base[i]++;                m--;                if(full[i]){                    full[i] = false;                    i++;                    continue;                }else{                    full[i] = true;                    break;                }             }         }         if(m==0)             System.out.println(base[0]);         else             System.out.println(base[0]-1);     } }

编辑于 2021-08-22 01:26:33 回复(0)
#include <bits/stdc++.h>
using namespace std;
int n,m;
bool check(int max_eat){
      int sum = max_eat;
      int t_eat = max_eat;
      for(int i = 1;i < n ; i++){
          if(t_eat%2!=0){
              t_eat = (t_eat+1) / 2;
          }else t_eat = t_eat/ 2;
          sum += t_eat;
      }
    return sum > m;
}


int main(void){
    cin>>n>>m;
    if(n==1){
        cout<<m<<endl;
        return 0;
    }
    int l = 1 , r = m;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    cout<< l - 1 ;
    return 0;
}
发表于 2021-05-17 15:45:51 回复(0)
参考“小冲冲”的编程思路写出来的C语言版本

#include <stdio.h>
#include <math.h>
int select();
int sum(int X);
unsigned int N,M,Y,L=1,H,X,V;
int main()
{   
 scanf("%u%u",&N,&M);
 V=select();
    printf("%d",V);
    
}
int select()
{
 H=M;
while(L<H)
 {
     X=(L+H+1)/2;
 Y=sum(X);
 if(Y==M)
 {
    return X;
 }
 else if(Y>M)
     H=X-1;
  else
     L=X;
  }
   return H;
}
int sum(int X)
{
        int sum=0;
        for(int i=0;i<N;i++)
        {
        sum=sum+X;
        X=(X+1)/2;
        }
        return sum;
    }
发表于 2020-10-06 18:16:14 回复(0)
var p=readline().split(' ').map(value=>+value);
let m=p[0],n=p[1];
let max=0;
let flag=0;
let start=0,end=n;
while(start<=end){
    let mid=Math.ceil((start+end)/2)
    let sum=mid;
    let num=mid;
    for(var j=1;j<m;j++){
       num=Math.ceil(num/2)
       sum+=num;
    }
   if(sum>n){
        end=mid-1;
   }else{
      start=mid+1;
       
   }
    sum=0;
}
print(start-1)
二分查找
发表于 2020-05-27 16:27:26 回复(0)
#include<iostream>
#include<algorithm>
#include<functional> 
using namespace std;

int cal(int cur, int n);
int binary_s(int n, int m);

int main(){
	int n, m;
	cin>>n>>m;
	cout<<binary_s(n, m)<<endl;
	return 0;
}

int binary_s(int n, int m){
	//二分查找
	int l = 1, r = m, mid;
	while(l < r){
		mid = (l + r + 1) >> 1;
		if(cal(mid, n) == m) 
			return mid;
		if(cal(mid, n) < m)
			l = mid;
		else
			r = mid - 1;
	}
	return l;
} 
int cal(int cur, int n){
	int sum = 0;
	for(int i = 1; i <= n; i++){
		sum += cur;
		cur = (cur + 1)>>1;
	}
	return sum;
}


发表于 2019-12-03 13:19:46 回复(0)

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 回复(2)
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)
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)
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)
找到前面几天最快到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)
#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 回复(23)
//二分查找,修改大佬们的边界,直接返回大于目标值的第一个下标  
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 回复(2)