单选题 适中
#24787

给定 n 根木头,第 i 根长度为 a[i] 。要切成不少于 m 段等长木段,求最大可能长度,则横线上应填 写( )。 const int MAXN = 100…

给定 n 根木头,第 i 根长度为 a[i] 。要切成不少于 m 段等长木段,求最大可能长度,则横线上应填 写( )。

const int MAXN = 100005;
Long Long a[MAXN];
int n, m;

bool check(Long Long x){
    Long Long cnt = 0;
    for(int i = 1; i <= n; i++){
        if(x == 0) return true;
        cnt += a[i] / x;
        if(cnt >= m) return true;
    }
    return false;
}

int main(){
    cin >> n >> m;
    Long Long mx = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    Long Long L = 1, r = mx;
    Long Long ans = 0;

    while(L <= r){
        Long Long mid = L + (r - l) / 2;

        if(check(mid)){
            ans = mid;
           ----------------------
        }else{
           ----------------------
        }
    }

    cout << ans << endl;
    return 0;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:A
解析
使用二分查找确定最大可能长度。定义左边界为最小可行长度,右边界为最长木头长度。每次取中点作为候选长度,通过检查函数判断是否能切出至少 m 段。检查函数统计每根木头可切段数,累加并比较与 m 的关系。若满足条件,说明当前长度可行,尝试更大的长度;否则尝试更小的长度。根据检查结果更新边界,持续缩小搜索范围直至收敛。