题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
typedef pair<int,int> PII;
vector<PII> a;
int n;
bool check_1(int x){
for(int i=0;i<a.size();i++)
if(a[i].first/x>a[i].second)
return false;
return true;
}
bool check_2(int x){
for(int i=0;i<a.size();i++)
if(a[i].first/x<a[i].second)
return false;
return true;
}
int find_l(int l,int r){
while(l<r){
int mid=(l+r)/2;
if(check_1(mid))
r=mid;
else
l=mid+1;
}
return r;
}
int find_r(int l,int r){
while(l<r){
int mid=(l+r+1)/2;
if(check_2(mid))
l=mid;
else
r=mid-1;
}
return r;
}
int main(){
cin>>n;
while(n--){
int x,y;
cin>>x>>y;
a.push_back({x,y});
}
sort(a.begin(),a.end());
int mi=find_l(1,a[0].first);
int ma=find_r(1,a[0].first);
cout<<mi<<" "<<ma<<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla