题目描述(浮点二分、最优化转判定)
- 二分分为,浮点二分和整数二分。
- 难点:最优化问题==》〉判定问题
- 一个问题可否使用二分法?设定最大裁剪长度为x,最短为l,最长为r。当取长度为mid=(l+r)/2时,
(1)可以裁m条,则,x$\in$[mid,r]
(2)不可以裁剪为m条,则,x$\in$(l,mid)
(此题中(l=0,r=1e9])
算法1
假定精度为r-l<1e-4
看题目中保留k位小数,则为r-l<1e-(k+2),其实可以任意小
JAVA 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int N = 100010,n=0,m=0;
static int[] g =new int[N];
public static boolean check(double x){
int cnt=0;
for(int i=0;i<n;i++){
cnt+=g[i]/x;
}
return cnt>=m;
}
public static void main(String[] args){
n = in.nextInt();
m = in.nextInt();
for(int i=0;i<n;i++){
g[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.println(String.format("%.2f",r));
}
}
算法2
精度可以设置为一个定值,
为1e7/(check函数的时间复杂度)=100
JAVA 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int N = 100010,n=0,m=0;
static int[] g =new int[N];
public static boolean check(double x){
int cnt=0;
for(int i=0;i<n;i++){
cnt+=g[i]/x;
}
return cnt>=m;
}
public static void main(String[] args){
n = in.nextInt();
m = in.nextInt();
for(int i=0;i<n;i++){
g[i]=in.nextInt();
}
double l=0,r=1e9;
for(int i=0;i<100;i++){
double mid =(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
System.out.println(String.format("%.2f",r));
}
}