题目:

考察点:

二分--假设某个值存在。

侃侃:

这道题可以说是二分中的一道模板题,我们先假设某个值成立,然后带入到已知条件中,判断当前值
是否满足所有的条件,若满足条件,看是否是最优的,如果不是最优的(还有更优的),就进一步缩小
范围,直到找到一个最优的值。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 10;

int a[maxn];

int n,k;

int Check(int x) {
    int ans = 0;
    // 假设当前满足条件的木棍长度是 x ,计算可以分成多少根木棍 
    for(int i = 1; i <= n; i ++) {
        ans += a[i] / x;
    }
    return ans;
}

int main(void) {
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i ++) {
        scanf("%d",&a[i]);
    }
    // 排序寻找一下最大值,缩减二分的范围 
    sort(a + 1,a + 1 + n);
    // 左端最少是 0 ,满足一定可分 
    int l = 0,r = a[n];
    while(l < r) {
        // + 1 防止出现死循环 
        int mid = (l + r + 1) >> 1;
        if(Check(mid) < k) r = mid - 1;
        else l = mid ;
    }
    printf("%d\n",r);
    return 0;
}

后记:

如有解释的不到位的地方,欢迎各位大佬在评论区留言。

欢迎各位大佬访问本菜鸡的博客:
https://www.cnblogs.com/prjruckyone/