剪绳子(浮点数二分)
有n条绳子,将其剪成m条长度相同的绳子(只能剪不能拼接),求出m根绳子绳子可以剪成的最大长度,保留两位小数
输入样例:
3 4
3 5 4
输出样例:
2.50
样例解释:
第一根和第三根分别裁剪出一根2.50长度的绳子,第二根剪成2根2.50长度的绳子,刚好4根。
思路:直接计算最大长度较困难,转换思路:枚举计算绳子剪成各个长度时是否能剪成m根。二分判断当前长度能否剪成m根,若不能满足,则应缩小每根绳子长度,直到满足题目精度要求。
#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
//计算绳子每根mid长时能否剪成m根
bool check(double mid)
{
int res = 0;
for(int i = 0; i < n; i++)
res += w[i] / mid;
return res >= 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 = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2lf", r); //返回l、r都可以
return 0;
}