题目描述

有 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

思路

思路:

使用二分法，判断能否剪出要求的绳子数量。
二分的是剪出的绳子长度。

开始状态：l=0,r=1e9,mid=(l+r)/2。l=0,r=1e9,mid=(l+r)/2。
判断能总共剪出长度为 mid 的绳子多少根：总共能剪出的根数=每一根绳子能剪出的根数之和。总共能剪出的根数=每一根绳子能剪出的根数之和。
如果能剪出长度为mid的绳子，则l=mid，如果不能，则r=mid。如果能剪出长度为mid的绳子，则l=mid，如果不能，则r=mid。
直到r−l<1e−3。

算法1

include [HTML_REMOVED]

using namespace std;

const int N=100010;

int n,m;
int w[N];

bool check(double mid)
{
int count=0;
for(int i=0;i[HTML_REMOVED]=m;
}

int main()
{

cin>>n>>m;
for (int i=0;i<=n;i++) cin>>w[i];

double l=0,r=1e9;
while (r-l>1e-4)
{
    double mid=(r+l)/2;
    if (check(mid)) l=mid;
    else r=mid;
}
printf("%.21f\n",r);
return 0;

}

时间复杂度

参考文献

C++ 代码

blablabla