题解：P12269 [蓝桥杯 2024 国 Python B] 切木棒

· · 题解

解题思路

看到求最大值最小，考虑二分答案。

切割次数越多，则最长的木棍长度可以越短，具备单调性。二分答案的思路可行。

因此二分最长木棍的长度 d，验证时对于原第 i 根长度为 l_i 的木棍，需要切割的次数为 \Large\frac{l_i}{d}，但是若 d\mid l_i 说明 d 能够整除 l_i 那么少切一次，因为刚好整除时，最后一刀切在木棍边缘。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int n, m, l[N];
bool check(int mid) {
    int cut = 0;
    for (int i = 1; i <= n; i++) {
        cut += l[i] / mid;
        if (l[i] % mid == 0) cut--; //重点：能整除的话少切一次
    }
    return cut <= m;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> l[i];
    int l = 1, r = 1e9, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << ans;
  return 0;
}