网线主管(二分答案)

网线主管(二分答案) 原题链接

心得：
二分答案步骤
step one：确定所求答案具有单调性，则可以使用二分答案(或者看到出现最大值最小或最小值最大之类的问题)
step two：写check函数，相当于是将可能的答案带入验证该答案是否满足题目的性质

二分答案的本质是二分地枚举答案

#include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10;
int n,k,l,r,res;
int line[N];//所有网线的长度

bool check(int res)
{
    int sum = 0;
    for (int i = 1;i <= n;i ++ ) sum += line[i] / res;

    if (sum < k) return true;
    else return false;
}

// 二分答案，根据枚举出的长度去算截出的数量，再根据数量调整长度
int main()
{
    cin >> n >> k;
    l = 1,r = 0;
    for (int i = 1;i <= n;i ++ ) {
        double x;
        cin >> x;
        line[i] = x * 100;//将米化成厘米
        if (line[i] > r) r = line[i];
    }
    //注意二分的边界问题
    while (l <= r){
        int mid = (l + r) / 2;
        if (check(mid)) r = mid - 1;
        else l = mid + 1;
    }

    printf("%.2lfn",(double)r / 100);
    return 0;
}