P9240 [蓝桥杯 2023 省 B] 冶炼金属 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二分做法:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4+10;
int n,a,b;
int v[N],cnt[N];
int check(int x){
for(int i=1;i<=n;i++){
int t=v[i]/x;
if(t<cnt[i]){
return 1;//x太大了
}else if(t>cnt[i]){
return 2;//x太小了
}
}
return 0;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i]>>cnt[i];
}
int mi=-1,mx=-1;
int l=1,r=1e9;
while(l<=r){
int mid=l+r>>1;
int t=check(mid);
if(t==0){
mx=mid;
l=mid+1;//因为x要尽可能大,故mid可以的话就尝试mid+1
}else if(t==1){
r=mid-1;
}else{
l=mid+1;
}
}
l=1,r=1e9;
while(l<=r){
int mid=l+r>>1;
int t=check(mid);
if(t==0){
mi=mid;
r=mid-1;//因为x要尽可能小,故mid可以的话就尝试mid-1
}else if(t==1){
r=mid-1;
}else{
l=mid+1;
}
}
cout<<mi<<" "<<mx;
return 0;
}