题目描述

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

输入描述:

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

输出描述:

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

题解

很明显，本题答案满足单调性并且判定贼好写@_@
如果我们把木块分的长度越长，那么我们能分成的段数就越少；反之，长度越短段数越多。所以对所有小于等于我们正解的数的长度都满足段数大于等于k，然后我们就可以快乐的二分啦~
顺便提一嘴，当时我初学的时候有一段时间一直不太理解为什么这种题可以用二分去解，后来某一天我突然想明白了，二分本来就是用来不断猜数来缩小范围的，对于这种题，我们也是一直在利用判定确定答案在我们猜的数的左边还是右边，本质上是一样的嘛，希望这些对初学者理解有帮助~

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,k;
int a[100500];
bool check(int x){
    ll sum=0;
    for(int i=1;i<=n;++i){
        sum+=a[i]/x;
    }
    return sum>=k;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    int l=1,r=1e9;
    int ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans);
}