AcWing 680. 剪绳子
原题链接
简单
作者:
长街听风
,
2021-01-24 14:11:59
,
所有人可见
,
阅读 291
Java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//绳子数量
int m = scanner.nextInt();//裁剪后的绳子数量
int[] arr = new int[n];
for(int i = 0; i < n;i++){
arr[i] = scanner.nextInt();
}
double l = 0,r = 1e9;//题目给出的绳子范围,故裁剪后的绳子长度肯定在该范围内
while(r - l > 1e-4){//题目要求保留两位小数,故根据经验精度应比题目要求多两位,即应保留四位
double mid = (l + r) / 2;//假定剪出的绳子长度为mid,另外浮点数不可写成l + r >> 1
if(check(arr,m,mid)) {//判断当裁剪的绳子的长度为mid时,能否剪出m根来
l = mid;//可以剪出m根来,则说明剪出的绳子可以更长,即继续到[mid,r]中找,如此逐渐压缩满足条件的范围,直到满足精度为止
}else {
r = mid;
}
}
System.out.println(String.format("%.2f",l));//输出结果保留两位小数
}
//判断当裁剪后绳子的长度为mid时,能否剪出m根来
private static boolean check(int[] arr,int m,double mid) {
int cnt = 0;
for(int i = 0 ;i < arr.length;i++ ){
cnt += arr[i] / mid;
}
return cnt >= m;
}
}