题目描述(整数二分)
要点:
- check函数=ture时,判断是l=mid还是r=mid,再根据此选择mid=(l+r+1)/2还是mid=(l+r)/2;
- 本题目中,mid越小,check越能成立,所以最大值要从右半边[mid,r]继续寻找,即l=mid,r=mid-1, mid=(l+r+1)/2;
算法1
时间复杂度
O(nlogn)
JAVA 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int n=0,k=0,N=100010;
static int[] h = new int[N], w = new int[N];
public static boolean check(int x){
long cnt = 0;
for(int i=0;i<n;i++){
cnt+=(long)h[i]/x*(w[i]/x);
if(cnt>=k) return true;
}
return false;
}
public static void main(String[] args){
n = in.nextInt();
k = in.nextInt();
for(int i=0;i<n;i++){
h[i] = in.nextInt();
w[i] = in.nextInt();
}
int l=1,r=100000;
while(l<r){
int mid = (l+r+1)/2;
if(check(mid)) l=mid;
else r = mid-1;
}
System.out.println(l);
}
}