题目描述
blablabla
样例
blablabla
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 10010;
int n;
int a[N], b[N];
bool check_min(int mid)
{
for (int i = 0; i < n; i++ )
if (a[i] / mid >b[i])//分成两半 符合性质的区间为<=;既在这个符合要求区间里面找最小值,该最小值
//就是所要求的
return false;
return true;
}
bool check_max(int mid)
{
for (int i = 0; i < n; i )
if (a[i] / mid < b[i])
return false;
return true;
}
int main()
{
scanf(“%d”, &n);
for (int i = 0; i < n; i ) cin >> a[i] >> b[i];
int l = 1, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
if (check_min(mid)) r = mid;
else l = mid + 1;
}
cout << l << ' ' ;
r = 1e9;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check_max(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla