[编程题]贪吃的小Q
- 热度指数：20591 时间限制：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并没有发现会真的越界导致出错）。
发表于 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 syss = list(sys.stdin.readline().split(' '))
n = int(s[0])
m = int(s[1])
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
发表于 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)
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)
问题信息
通过挑战的用户
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
