172、木棒切割問題
https://sunnywhy.com/problem/172
題目描述
給出n根木棒的長度，現在希望通過切割它們來得到至少k段長度相等的木棒（長度必須是整數），問這些長度相等的木棒的最大長度，
輸入描述
第一行為兩個正整數n、k（1≤n≤103、1≤k≤108），分別表示木棒的根數、需要得到的長度相等的木棒根數；
第二行為n個整數（1≤每個整數≤105），表示木棒的長度，
輸出描述
一個整數，表示木棒的最大長度，如果無法達成，此時最大長度為
0，
思考
如果通過暴力解法，那么復雜度為\(O(n^2)\)，每輪選擇一個長度遍歷每根繩子，
已知木棒分割的長度為正整數，且位于\([1,max(每根繩子的長度)]\)區間，當前為有序序列，求解至少k段長度相等木棒時，木棒的最大長度，
有序序列+求第一個滿足某條件的元素的位置 => 二分法
已知木棒分割的長度序列從小到大，那么每個木棒長度對應的木棒段數序列從大到小，
那么求木棒的最大長度，實際上在求最后一個 >= k 的木棒段數此時的木棒長度 ，
但二分法是求第一個滿足某條件的元素位置，為什么呢？不妨先試著撰寫求最后一個滿足某條件元素位置的二分法，
假定序列從小到大排列，可以很容易寫出下面三種情況，但在測驗程序中，往往會出現死回圈或沒有輸出的現象，
第1、3種情況無論如何也會讓 \(left < right\) 不成立從而退出\(while\)回圈，
那么很可能在第2種情況的時候陷入了死回圈，求解一下死回圈成立的條件，
\(\frac{left+right}{2} = left \\ \frac{right}{2} = \frac{left}{2} \\ \text 這是C語言的整除\)
二分法求解給定的\(while\)條件是\(left < right\)，顯而易見，當left、right為相鄰的奇偶時，且當 \(A[mid] == x\) 時，會無限死回圈，每輪都會進入第2種情況，
所以牢記二分法用于尋找有序序列第一個滿足某條件的元素的位置，
題解很簡單，我們只需要求第一個分段數小于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;
// 加載資料
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;
}
二分法固定模板
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/520666.html
標籤：其他