算法可视化
入门执行逻辑
二分答案:切木棍
把长度 10、8、7 的木棍切成每段长度相同的小段,要求正好 3 段,求每段最长能是多少。答案在 1~10 之间二分。
main.cpp第 2 行
1// 二分答案: 木棍 10, 8, 7 切 3 段, 求最大段长
2int check(int len) { // 每根按 len 切, 能得几段
3 int cnt = 0;
4 for (int x : sticks) cnt += x / len;
5 return cnt;
6}
7int lo = 1, hi = 10; // 答案范围
8while (lo < hi) {
9 int mid = (lo + hi + 1) / 2;
10 if (check(mid) >= 3) lo = mid; // 能切够, 试试更长
11 else hi = mid - 1; // 切不够, 缩短
12}
13// 答案: lo = 7
变量表2 个变量
木棍[10, 8, 7]
目标段数3
1/12
木棍长度 10、8、7,需要切成 3 段,求每段最长能是多少
1 / 12