题目描述
有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根。
解析
这道题代码很好写,关键看自己能不能想到用二分来做,想到的话基本上就能做出来了
==怎么想到用二分来做呢?(y总教的)==
1:首先看题型如果是求最优解,而且很难能直接求解
2:那就考虑可不可以加一个条件把最优解转化为判定问题,可以的话思路就会简单很多
3:然后在考虑可不可以用二分,判断一下中点,能不能根据中点的情况,把区间的范围缩小一半,如果可以就可以用二分来做,否则是不可以的;
比如说这道题,让我们把n根绳子剪成等长的m根,就很难想到怎么做
但是如果加一个条件:我们知道一根m是多长,那就很好做了,直接用n根绳子都除以m,然后向下取整在加起来,然后会分为两种情况
1:如果加起来大于等于m,说明是成立的,答案在右半边,因为左半边肯定是全部满足的,会让m越来越小,而我们找的是最长的,所以应该去右半边找,l = mid
2:如果加起来小于m,说明当前m的长度是不合适的,太长了,我们就要去左半边找,r = mid
那思路不就来了嘛,上代码
JAVA代码
import java.util.Scanner;
public class Main{
static int N = 100010;
static int n,m;
static int[] a = new int[N];;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
for(int i = 0; i < n; i ++) a[i] = in.nextInt();
double l = 0, r = 1e9; //基本上跟二分模板一模一样
while(r - l > 1e-4){
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
System.out.print(String.format("%.2f",l));
}
private static boolean check(double mid)
{
int count = 0;
for(int i = 0; i < n; i ++){
count += a[i] / mid;
}
return count >= m;
}
}