华华给月月准备礼物

Solution

根据题目大意，很快可以发现，如果我们枚举一个 ，可以在这个 情况下求到 根木棍，我们就希望能不能再求更大的 ；
否则，可行解一定比当前ans更小。符合单调特性，采取二分的思路。

再说说我对二分的心得
二分大致可以分为两种思路，范围缩小让 逼近答案

while (l < r) {
        ll mid = r + l >> 1;
        if (a[mid]>=x)    r = mid;
        else     l = mid + 1;
    }

范围缩小让 逼近答案

while (l < r) {
        ll mid = r + l + 1 >> 1;
        if (a[mid]<=x)    l = mid;
        else     r = mid - 1;
    }

这两种区别在于求 的时候，第一种 不会取到 这个值；
第二种 不会取到这个值。
根据不同题目选择合适的方法，去处理无解的情况。
总而言之， 正确写出这种二分的流程是：

1. 通过分析具体问题，确定左右半段哪一个是可行区间， 以及mid 归属哪一半段。
2. 根据分析结果，选择"r= mid, l = mid + 1, mid = (l + r)>>1" 和"l= mid, r = mid -1, mid= (l + r+ 1)>>1" 两个配套形式之一。
3. 二分终止条件是l== r, 该值就是答案所在位置。

时间复杂度O( )

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 7;
ll a[N];
int n,k;

bool judge(ll x){
    ll cnt=0;
    for(int i=1;i<=n;++i)    cnt+=a[i]/x;
    return cnt>=k;
}

int main (){
    scanf("%d %d",&n,&k);
    for(int i = 1; i <= n; ++i)
        scanf("%lld",&a[i]);

    //二分求解，因为取不到0，并且我们让合法的答案保持在l中，选择第一种二分方法
    ll l=0,r=1e9+7;
    while(l<r){
        ll mid=r+l+1>>1; //ll可以吧位运算写简单点，不然只有用r-（r-l）/2了
        if(judge(mid))    l=mid;
        else     r=mid-1;
    }
    printf("%lld\n",l);
    return 0;
}