转化比的最大值实际是每组金属冶炼转化值的最小值
输入时顺带求出最大值,然后以最大值为右端点,1为左端点二分
check函数用于检查mid是否满足每组冶炼比
如果a/mid<=b说明mid能满足这组金属冶炼,最后看sum是否等于n,等于说明满足所有组,return true,然后l=mid向左二分寻找更小的值,如果sum不等于n说明这个 mid太小了,比如说输入3 75 3 53 2 59 2也就是测试样例,如果mid=19第三组能练出来3个,比题目给的2个大,这说明19一定小于这个最小值(最小值一定可以正好让所有组都满足a/mid=b),return false 然后向右找,反复循环最后一定能找到最小值;
import java.util.;
import java.io.;
import java.math.*;
public class Main{
static Scanner sc=new Scanner(System.in);
static int n=0;
static int a[]=new int[100010];
static int b[]=new int[100010];
public static boolean check(int mid) {
int sum=0;
for(int i=0;i<n;i++) {
if(a[i]/mid<=b[i]) {
sum++;
}
}
if(sum==n) {
return true;
}else {
return false;
}
}
public static void main(String[]args) {
n=sc.nextInt();
int max=(int)1e9;
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
b[i]=sc.nextInt();
int c=a[i]/b[i];
if(max>c) {
max=c;
}
}
int l=1;
int r=max;
while(l<r) {
int mid=l+r>>1;
if(check(mid)) {
r=mid;
}else {
l=mid+1;
}
}
System.out.println(l+" "+max);
}
}