切绳子【洛谷P1577】【二分】

切绳子【洛谷P1577】【二分】

题目描述

有 N 条绳子，它们的长度分别为 Li。如果从它们中切割出 K 条长度相同的绳子，这 K 条绳子每条最长能有多长？答案保留到小数点后 2 位(直接舍掉 2 位后的小数)。

输入格式

第一行两个整数 N 和 K，接下来 N 行，描述了每条绳子的长度 Li 。

对于 100 的数据 0<Li≤100000.00,0<n≤10000,0<k≤10000

输出格式

切割后每条绳子的最大长度。答案与标准答案误差不超过 0.01 或者相对误差不超过 1% 即可通过。

输入

4 11
8.02
7.43
4.57
5.39

输出

2.00

代码

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

int n, k;
double x[10005];

int f(double l){
    
    int ans = 0;
    for (int i = 0; i < n; ++i) {
    
        ans += floor(x[i] / l);
    }
    return ans;
}

signed main(){
    
    cin>>n>>k;
    for (int i = 0; i < n; ++i) {
    
        cin>>x[i];
    }
    double l = 0, r = 100000.00, mid;
    while (r - l > 1e-3){
    
        mid = (l + r) / 2;
        if (f(mid) >= k)
            l = mid;
        else
            r = mid;
    }
    printf("%.2lf", floor(r * 100) / 100);
    return 0;
}