AcWing 4956. 冶炼金属
原题链接
简单
作者:
stc
,
2024-02-28 23:56:00
,
所有人可见
,
阅读 25
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4+10;
int n;
int a[N],b[N];
// 第一个满足要求的(尽可能小)
int bs1(){
int l = 1, r = 1e9;
while(l<r){
int mid = (l+r) >> 1;
int i = 0;
for(;i<n;i++){
if(a[i]/mid != b[i]) break;
}
if(i==n) r = mid;
else if(a[i]/mid < b[i]) r = mid-1;
else l = mid + 1;
}
return l;
}
// 最后一个满足要求的(尽可能大)
int bs2(){
int l = 1, r = 1e9;
while(l<r){
int mid = (l+r+1) >> 1;
int i = 0;
for(;i<n;i++){
if(a[i]/mid != b[i]) break;
}
if(i==n) l = mid;
else if(a[i]/mid > b[i]) l = mid + 1;
else r = mid - 1;
}
return l;
}
// O(nlogA)=O(9*10^4*log10)
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<n;i++) cin>>a[i]>>b[i];
int v1 = bs1(),v2 = bs2();
cout<<v1<<" "<<v2<<endl;
return 0;
}