单选题 适中
#19820

小杨要把一根长度为 L 的木头切成 K 段,使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段,他用二分法找到满足条件的最小 x ( x 为正整数)…

小杨要把一根长度为 L 的木头切成 K 段,使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段,他用二分法找到满足条件的最小 x ( x 为正整数),则横线处应填写( )。

// 判断:在不超过 K 次切割内,是否能让每段长度 <= x 
bool check(int L, int K, int x) { 
    int cuts = (L - 1) / x; 
    return cuts <= K; 
} 
// 二分查找最小可行的 x 
int binary_cut(int L, int K) { 
    int l = 1, r = L; 
    while (l < r) { 
        int mid = l + (r - l) / 2; 
        ________________________________ // 在此处填入代码 
    } 
    return l; 
} 
int main() { 
    int L = 10; // 木头长度 
    int K = 2; // 最多切 K 刀 
    cout << binary_cut(L, K) << endl; 
    return 0; 
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析
确定最小的正整数 x,使得将长度为 L 的木头切分为 K 段后,每段长度不超过 x。使用二分法在合理范围内查找 x,每次取中点 mid 作为候选值,通过 check 函数判断在最多 K 次切割下是否能保证所有段长度 ≤ mid。若判断成立,则说明 mid 可行,搜索更小的值;否则搜索更大的值。更新边界时需保持搜索区间的有效性,确保最终收敛到最小可行解。