AcWing 4956. 冶炼金属
原题链接
简单
作者:
神的在场证明
,
2024-04-12 11:32:26
,
所有人可见
,
阅读 3
C++ 代码
#include<iostream>
using namespace std;
#define int long long
const int N = 1e4 +10;
int n, maxx;
int a[N], b[N];
//判断 A - X * B 的结果是否 小于 等于 X(最大)
bool check1(int x){
for(int i = 0; i < n; i++){
if(a[i] - x*b[i] >= x) return false;
}
return true;
}
//判断 A/X 是否 大于等于 B
bool check2(int x){
for(int i = 0; i < n; i++){
if(a[i] < b[i]*x) return false;
}
return true;
}
signed main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
for(int i = 0; i < n; i++) maxx = max(maxx, a[i]);
//第一 个二分 求满足条件的最小值
int l = 0, r = maxx;
while(l < r){
int mid = l +r >> 1;
if(check1(mid)) r = mid;
else l = mid + 1;
}
cout << l << " " ;
//第二个二分 求满足条件的最大值
r = maxx;
while(l < r){
int mid = l + r + 1 >> 1;
if(check2(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}