算法1
(暴力枚举)
只能过掉一部分,混分使用
时间复杂度
O(1e10)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n;
int a[N], b[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
// 暴力过一部分数据
for (int i = 1; i <= 1e6; i++) // 先枚举1e6个v,过掉一部分的数据
{
bool flag = true; // 标记一下当前v都合法
for (int j = 1; j <= n; j++) // 开始循环冶炼次数
{
if (b[j] != (a[j] / i)) // 此时i就是v
{
flag = false;
break;
}
}
if (flag)
{
cout << i << " "; // 从1开始枚举,算出最小边界值
break;
}
}
for (int i = 1e6; i >= 1; i--) // 从1e6开始枚举,算出最大边界值
{
bool flag = true; // 标记一下当前v都合法
for (int j = 1; j <= n; j++) // 开始循环冶炼次数
{
if (b[j] != (a[j] / i)) // 此时i就是v
{
flag = false;
break;
}
}
if (flag)
{
cout << i;
break;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
算法2
(二分)
时间复杂度
O(nlonN)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n;
int a[N], b[N];
bool check_min(int mid)
{
for (int i = 1; i <= n; i++)
{
if (b[i] < a[i] / mid) return false; // 此时mid看作v来找条件比较
}
return true; // 遇到第一个值就是最小的, 返回true
}
bool check_max(int mid)
{
for (int i = 1; i <= n; i++)
{
if (b[i] > a[i] / mid) return false;
}
return true; // 遇到第一个值就是最大的, 返回true
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
// 求最小值
int lmin = 1, rmin = 1e9;
while (lmin < rmin)
{
int mid = lmin + rmin >> 1;
if (check_min(mid)) rmin = mid;
else lmin = mid + 1;
}
// 求最大值
int lmax = 1, rmax = 1e9;
while (lmax < rmax)
{
int mid = lmax + rmax + 1 >> 1;
if (check_max(mid)) lmax = mid;
else rmax = mid - 1;
}
cout << lmin << " " << rmax;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}