返回题解分享
讨论 / 题解分享/ 帖子详情

冶炼金属(编程题) - 题解

#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int N = 1e4 + 10;

int n;
int A[N], B[N];

bool check1(int x)
{
	for (int i = 1; i <= n; i++)
	{
		if (A[i] / x > B[i])
			return true;
	}
	return false;
}

bool check2(int x)
{
	for (int i = 1; i <= n; i++)
	{
		if (A[i] / x < B[i])
			return false;
	}
	return true;
}

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> A[i] >> B[i];

	int l_min = 1 - 1, r_min = 1e4 + 1;
	while (l_min + 1 != r_min)
	{
		int mid = (l_min + r_min) >> 1;
		if (check1(mid)) l_min = mid;
		else r_min = mid;
	}

	int l_max = r_min, r_max = 1e4 + 1;
	while (l_max + 1 != r_max)
	{
		int mid = (l_max + r_max) >> 1;
		if (check2(mid)) l_max = mid;
		else r_max = mid;
	}

	cout << r_min << ' ' << l_max;
}

signed main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	solve();

	return 0;
}
0 回复 0 转发 0 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!