二分查找
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 1e4 + 1;
int N, A[MAX_N], B[MAX_N];
bool check_min(int V)
{
for(int i = 1;i <= N;++i)
{
if(A[i] / V > B[i])
{
return false;
}
}
return true;
}
bool check_max(int V)
{
for(int i = 1;i <= N;++i)
{
if(A[i] / V < B[i])
{
return false;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin>>N;
for(int i = 1;i <= N ;++i)
{
cin>> A[i] >> B[i];
}
int L = 1,R = 1000000000,V_min;//先找最小值
while(L <= R)
{
int mid = L + R >> 1;
if(check_min(mid))//如果复符合要求
{
V_min = mid;
R = mid - 1;
}
else
{
L = mid + 1;
}
}
L = 1, R = 1000000000;
int V_max;
while(L <= R)
{
int mid = L + R >> 1;
if(check_max(mid))
{
V_max = mid;
L = mid + 1;
}
else
{
R = mid - 1;
}
}
cout<<V_min<<" "<<V_max<<endl;
return 0;
}
0 回复
0 转发
1 喜欢
0 阅读



