思路
v的最小值和最大值的区间肯定是单调的,在区间内的值满足条件,其他则不满足条件。所以可以用二分
check函数:
check1求v的最小值,v越小,a/v越大,但是a/v再大也不能大于b,所以当a/v>b时返回false
check2求v的最大值,v越大,a/v越小,但是a/v再大也不能小于b,所以当a/v<b时返回false
代码
#include<iostream>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e4+10;
int n;
int a[N],b[N];
bool check1(int mid){
//求最小值
for(int i=0;i<n;i++){
if((a[i]/mid)>b[i]) return false;
}
return true;
}
bool check2(int mid){
//求最大值
for(int i=0;i<n;i++){
if((a[i]/mid)<b[i]) return false;
}
return true;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
int l=1,r=1e9;
while(l<r){
int mid=l+r>>1;
if(check1(mid)) r=mid;
else l=mid+1;
}
cout<<l<<" ";
r=1e9;
while(l<r){
int mid=l+r+1>>1;
if(check2(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}