华华给月月准备礼物

题目描述：

链接：https://ac.nowcoder.com/acm/problem/23049
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？

输入描述：

第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N个正整数Li​表示每根木棍的初始长度。

输出描述：

输出一行一个非负整数表示每根木棍的最大长度。

数据范围

solution

二分搜索答案
分析一下时间复杂度，在1-1e9范围内二分查找，最多执行32次，然后遍历每根木棍长度，判断能最多能形成当前答案的木棍的数量，每次最多循环2e5次，判断当前答案是否符合要求，符合要求先记录下来，在缩小范围继续查找。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[200005];
int l=1,r=1000000000,mid,result;
bool check(int x)
{
    long long ans=0;
    for(int i=0;i<n;i++)
        ans+=a[i]/x;
    return ans>=k;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))
        {
            result=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    cout<<result;
}