题目描述
有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根。
算法1
使用某个长度去尝试能否剪出达到要求的绳子根数。
如果符合,则尝试增加长度,如果不符合则减少长度在尝试,直到找到边界值
有序查找 明显的使用二分
不过要注意double的二分模板稍有区别
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int a[N];
bool check(double mid){
int s = 0;
for(int i =0; i < n;i++){
s += a[i]/mid;
if(s >= m) return true;
}
return false;
}
int main(){
cin >> n >> m;
for(int i =0 ;i < n; i++){
cin >> a[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("%.2f\n",r);
return 0;
}