每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数,表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。
输出一个数表示小Q第一天最多能吃多少块巧克力。
3 7
4
#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; }
二分查找求第一天可能吃的最多糖数
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)
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; } }
二分查找法:修改了一下大佬的边界条件
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));
}
}
在域外創音大佬的基础上做了一点修改:
#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并没有发现会真的越界导致出错)。
#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))
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)二分查找
#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; }
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))
//二分查找,修改大佬们的边界,直接返回大于目标值的第一个下标
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;
}
}
import syss = list(sys.stdin.readline().split(' '))
return count
#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; }
二叉树遍历解决问题
#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; }
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))
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 |
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))
#include <stdio.h> int main(void) { int p[20] = {1, 1}, day, sweet; int ans = 0; for (int i = 2; i < 20; i++) { p[i] = p[i - 1] * 2; // printf("%d ", p[i]); } for (int i = 2; i < 20; i++) { p[i] = p[i] * 2 - 1; // printf("%d ", p[i]); } scanf("%d %d", &day, &sweet); if (day > 20) { sweet -= (day - 19); day = 19; } while (sweet > 0) { while (day && sweet && p[day] > sweet) { day--, sweet--; } if (day == 0) { ans++; break; } if (sweet == 0) { break; } ans += 1 << (day - 1); sweet -= p[day]; } printf("%d\n", ans); return 0; }