1.题目描述
小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力。
- 输入描述：
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。 - 输出描述：
输出一个数表示小Q第一天最多能吃多少块巧克力。 - 输入示例：
3 7 - 输出示例：
4
2.题目解析
- 思路
- 因为每天至少要吃
1块巧克力，所以第1天最多吃M-(N-1)块巧克力 - 从
M-(N-1)到1，计算该吃法是否满足条件，满足条件即跳出循环
- 因为每天至少要吃
3.参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 0; // 出差的天数
int m = 0; // 巧克力的数量
scanf("%d%d",&n,&m);
int max = m-(n-1);// 假设第一天吃的数量
while(true){
int sum = max;
int pre = max;
for(int i=1;i<n;++i){
sum += pre / 2;
pre = pre / 2;
}
if(sum == m){// 判断所有天数吃的数量是否是给定数量
printf("%d\n",max);
break;
}else{
--max;
}
}
return 0;
}
二分查找
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 0; // 出差的天数
int m = 0; // 巧克力的数量
scanf("%d%d",&n,&m);
int first = m-(n-1);// 第一天最多吃的数量
int last = 1;// 第一天最少吃的数量
while(first >= last){
int mid = (first+last+1)/2;
int sum = mid;
int pre = mid;
for(int i=1;i<n;++i){
sum += (pre+1) / 2;
pre = (pre+1) / 2;
}
if(sum > m){
first = mid-1;
}else{
last = mid+1;
}
}
printf("%d\n",first);
return 0;
}
