华华给月月准备的礼物

题目：原题链接

题解：

这是一道纯血的二分搜索题。题目中要求切出k根等长木棍，输出可能的最大长度。于是我们可以使用二分遍历所有可能的木棍长度，判断当前长度是否满足来缩减范围。由于最大的可能长度为1e9，所以时间复杂度并不是很高，加上遍历判断的过程，复杂度只有O(nlogn).
其余的介绍在代码中以注释的形式给出。

拓展

附上两种常用滴二分模板：

int search(int l,int r){
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))
            l=mid+1;
        else r=mid;
    }
    return l;
}

int search(int l,int r){
    while(l<r){    
        int mid=l+r+1>>1;//当区间划分为[l,mid-1],[mid,r]时，为了防止死循环，要加上1
        if(check(mid))
            l=mid;
        else r=mid-1;
    }
    return l;
}

AC代码

#include<iostream>
#include<algorithm>
using namespace std ;

int stick[200010];//存放木条长度
int n,k;

int judge(int x){//判断函数，当剪出长度为x的木条数小于需要时，返回false
    int res=0;
    for(int i=1;i<=n;i++){
        res+=(stick[i]/x);
    }
    return res>=k;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%d",&stick[i]);
    }

    int l=0,r=1e9+10;
    while(l<r){
        int mid=(l+r+1)>>1;//可以理解为（l+r+1）/2
        if(judge(mid))//当剪出长度木条大于或者等于k，至少mid和它右边的数才有可能是最大值
            l=mid;
        else r=mid-1;
    }
    cout<<r<<endl;//l和r相同，输出一个就可
    return 0;
}