下面是题目复述:
有 n 条绳子,它们的长度分别为 Li,如果从它们中切割出 m 条长度相同的绳子,这 m 条绳子每条最长能有多长?
输入格式
第一行两个整数 n 和 m。
接下来 n 行,每行一个实数,描述了每条绳子的长度 Li。
数据范围:≤n≤m≤10^4,1≤Li≤10^5。
输出格式
切割后每条绳子的最大长度,保留 66 位小数。
Sample Input
4 11
8.02
7.43
4.57
5.39
Sample Output
2.00
分析过程
- 考虑二分算切割出来的绳子的长度。
- 判断的时候看给出的绳子长度一共能截断出来多少根绳子,若比m多,则切割的绳子长度可以延长,如果少,则绳子的长度需要减少。
注意: 用排序算绳子的最大值会超时,建议直接在输入的时候找到最大值用来确定二分范围。
下面是AC代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
const int N=1e5+10;
using namespace std;
double m;
int n;
double s[N];
bool check (double x)
{
int sum=0;
for(int i=0;i<n;i++)
{
sum+=s[i]/x;
}
if(sum>=m) return true;
else return false;
}
double bsearch(double l,double r)
{
while (r-l>1e-8)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
return l;
}
int main()
{
double ma=0;
scanf("%d %lf",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%lf",&s[i]);
ma=max(s[i],ma);
}
double num=bsearch(0,ma);//二分答案长度
printf("%.6f\n",num);
return 0;
}