binary search
需求
小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天的一半，但是他又不想在父母回来之前把巧克力吃完，请问他第一天最多能吃多少块蛋糕
N<=50000,N<M<100000
示例
输入：
3 7
4 7
输出：
4
3
解题思路
- 本题可以想成，我从1～M块巧克力中选出一块来，这块巧克力就是我第一天最多能吃的巧克力
- 那这个选出来的有什么条件需要满足呢：要满足我选出来的这个是第一天最多能吃的，那么就是最后几天都要吃最少的，但又要满足不少于前一天的一半，所以就是刚好吃前一天的一半。注意的是，这里要吃就是一整块，不存在是吃几分之一块，强迫症很舒服
- 那就是我用二分查找法去选一个巧克力数出来，去看是否满足条件
- 这个条件呢就是你每天吃的加起来刚好或者说小于你的总巧克力数，不能饿死嘛，保证每天都有吃的
代码实现
package main
import (
"fmt"
"math"
"os"
)
// 出差天数
var N int
// 巧克力个数
var M int
func main() {
for {
num, err := fmt.Scanf("%d %d", &N, &M)
if num != 2 || err != nil {
fmt.Println(err)
os.Exit(1)
}
search()
}
}
// 假如第一天吃n个,计算总共吃了多少个
func sum(n int) (m int) {
for i := 0; i < N; i++ {
m =m + n
n = int(math.Ceil(float64 (n) / 2))
}
return m
}
// 二分查找满足的条件
func search() {
begin := 1
end := M
mid := 0
if N == 1 {
fmt.Println(M)
return
}
for i := 0; i < M; i++ {
if begin > end {
break
}
// 向上取整，要吃就要吃一整个
mid = int(math.Ceil(float64(end+begin) / 2))
if sum(mid) == M {
fmt.Println(mid)
return
}
if sum(mid) < M {
// 取等于是因为防止没有正好吃完的情况，需要取mid的值
begin = mid
} else {
end = mid - 1
}
}
// 这是有剩余巧克力的情况
fmt.Println(mid)
}