AcWing 4956. 冶炼金属
原题链接
简单
作者:
on1
,
2024-02-18 21:20:57
,
所有人可见
,
阅读 37
一般二分写法
#include <iostream>
#include <cstring>
#include <algorithm>
#define ioputs ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using LL = long long;
const int N = 1e4 + 100;
LL a[N], b[N], n;
bool checklower(LL mid)
{
for (int i = 0; i < n; i ++ )
{
if (a[i]/mid > b[i]) return 0; // 找小了
else continue;
}
return 1;
}
bool checkupper(LL mid)
{
for (LL i = 0; i < n; i ++ )
{
if (a[i]/mid < b[i]) return 0; // 找大了
else continue;
}
return 1;
}
signed main()
{
ioputs;
LL r = INF, l = 1;
cin >> n;
for (int i = 0 ; i < n; i ++ ) cin >> a[i] >> b[i];
while (l < r)
{
LL mid = l + r >> 1;
checklower(mid) ? r = mid : l = mid + 1;
}
LL rr = INF, ll = 1;
while (ll < rr)
{
LL mid = ll + rr + 1 >> 1;
checkupper(mid) ? ll = mid : rr = mid - 1;
}
cout << r << " " << ll << endl;
return 0;
}