题目描述

680.剪绳子

有 N 根绳子，第 i 根绳子长度为 Li，现在需要 M 根等长的绳子，你可以对 N 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 M 根绳子最长的长度是多少。

输入格式
第一行包含 2 个正整数 N、M，表示原始绳子的数量和需求绳子的数量。

第二行包含 N 个整数，其中第 i 个整数 Li 表示第 i 根绳子的长度。

输出格式
输出一个数字，表示裁剪后最长的长度，保留两位小数。

数据范围
1≤N,M≤100000,
0<Li<109

样例

输入样例：
3 4
3 5 4


输出样例：
2.50


样例解释
第一根和第三根分别裁剪出一根 2.50 长度的绳子，第二根剪成 2 根 2.50 长度的绳子，刚好 4 根。

C++ 代码

# include <iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N];

int n,m;

int check(double temp)
{
    int res = 0;
    for(int i = 0 ; i < n ; i++)
    {
        res += (a[i] / temp);  
    }
    return res;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 0 ; i < n ; i++)
    {
        scanf("%d",&a[i]);
    }
    double l = 0;
    double r = 1e9 + 10;
    while(r - l >= 1e-5)
    {
        double temp = (l + r) / 2;
        if(check(temp) >= m)
        {
            l = temp;
        }
        else
        {
            r = temp;
        }
    }
    printf("%.2lf\n",r);
    return 0;
}