C++算法之旅、02 從木棒切割問題領(lǐng)悟二分法精髓 _生活百科

172、木棒切割問題

https://sunnywhy.com/problem/172
題目描述
給出n根木棒的長度，現(xiàn)在希望通過切割它們來得到至少k段長度相等的木棒（長度必須是整數(shù)），問這些長度相等的木棒的最大長度。
輸入描述
第一行為兩個正整數(shù)n、k（1≤n≤103、1≤k≤108），分別表示木棒的根數(shù)、需要得到的長度相等的木棒根數(shù)；
第二行為n個整數(shù)（1≤每個整數(shù)≤105），表示木棒的長度。
輸出描述
一個整數(shù)，表示木棒的最大長度。如果無法達成，此時最大長度為0 。

思考【C++算法之旅、02 從木棒切割問題領(lǐng)悟二分法精髓】如果通過暴力解法，那么復(fù)雜度為\(O(n^2)\) 。每輪選擇一個長度遍歷每根繩子。
已知木棒分割的長度為正整數(shù)，且位于\([1,max(每根繩子的長度)]\)區(qū)間。當(dāng)前為有序序列。求解至少k段長度相等木棒時，木棒的最大長度。
有序序列+求第一個滿足某條件的元素的位置 => 二分法
已知木棒分割的長度序列從小到大，那么每個木棒長度對應(yīng)的木棒段數(shù)序列從大到小。
那么求木棒的最大長度，實際上在求最后一個 >= k 的木棒段數(shù)此時的木棒長度。
但二分法是求第一個滿足某條件的元素位置，為什么呢？不妨先試著編寫求最后一個滿足某條件元素位置的二分法。
假定序列從小到大排列，可以很容易寫出下面三種情況。但在測試過程中，往往會出現(xiàn)死循環(huán)或沒有輸出的現(xiàn)象。

文章插圖
第1、3種情況無論如何也會讓 \(left < right\) 不成立從而退出\(while\)循環(huán) 。
那么很可能在第2種情況的時候陷入了死循環(huán)，求解一下死循環(huán)成立的條件。
\(\frac{left+right}{2} = left \\ \frac{right}{2} = \frac{left}{2} \\ \text 這是C語言的整除\)
二分法求解給定的\(while\)條件是\(left < right\) 。顯而易見，當(dāng)left、right為相鄰的奇偶時，且當(dāng) \(A[mid] == x\) 時，會無限死循環(huán)，每輪都會進入第2種情況。
所以牢記二分法用于尋找有序序列第一個滿足某條件的元素的位置。
題解很簡單，我們只需要求第一個分段數(shù)小于k的木棒長度然后減1即可。
解法

// https://sunnywhy.com/problem/172// 考察二分查找#define _CRT_SECURE_NO_WARNINGS#include <cstdio>int countSticks(int ans[], int len, int sep) {int total = 0;for (int i = 0; i < len; i++) {total += ans[i] / sep;}return total;}int main() {int n, k, ans[1010], max = 0;// 加載數(shù)據(jù)scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) {scanf("%d", &ans[i]);if (ans[i] > max) {max = ans[i];}}// 邏輯處理int mid, left = 1, right = max;while (left < right) {mid = (left + right) / 2;if (countSticks(ans, n, mid) < k) {right = mid;} else {left = mid + 1;}};printf("%d\n", --left);return 0;}

二分法固定模板