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

dendky · 2025-04-24 20:24:34 · 题解

思路

看见题目求最长的最短，考虑二分答案。二分中的 mid 即为最长木棍的最小值，只需用 \left \lceil \frac{a_i}{mid} \right \rceil 挨个计算一遍，求出修改次数判断是否小于等于 m 即可。最后输出左边界为答案。

注意：如果 a_i \bmod mid = 0 那么修改次数要减一，因为在这种情况下最后一刀会砍空，就是没砍到。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[300005];
bool check(int x) {
    int sum=0;
    for (int i=1; i<=n; i++) {
        sum+=a[i]/x;
        if (a[i]%x==0) sum--;
    }
    return sum>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>>a[i];
    int l=1, r=1e9;
    while (l<=r) {
        int mid=l+r>>1;
        if (check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}