每日打卡-5.2

一.问题描述

小A是某工地的计算工程师。工地现有 n 根钢管，第 i 根钢管的长度为 ai。

现在想用这 n 根钢管来做一个支撑用的柱子。我么可以切割这些钢管成为更短的钢管，但是不能缝合两根钢管。为了安全起见，柱子必须用 至少 k 根长度相同的钢管加上混凝土制成，并且要求钢管长度必须为 整数。

小A想知道，这个柱子最高能建成多高（钢管可以有剩余）。

注：1<=n，k<=1e5，1<=ai<=1e8

二.设计思路

这里我们对答案进行二分，找到一个可行的答案即可！最后输出的是 r - 1，因为我们保证的是 l 是可行的范围， r 是不可行的范围，最后需要减一，使得答案是可行的。

三.流程图

四.伪代码 

1

五.代码实现 

1#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int l = 0, r = 100000001;
    while(l < r){
        int mid = (l + r) >> 1;
        int cnt = 0;
        for(int i = 0; i < n; i++){
            cnt += a[i] / mid;
        }
        if(cnt >= k){
            l = mid + 1;
        }else{
            r = mid;
        }
    }
    cout << r - 1;
    return 0;
}