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

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

二分查找

#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;

const int MAX_N = 1e4 + 1;
int N, A[MAX_N], B[MAX_N];

bool check_min(int V)
{
	for(int i = 1;i <= N;++i)
	{
		if(A[i] / V > B[i])
		{
			return false;
		}
	}
	return true;
}
bool check_max(int V)
{
	for(int i = 1;i <= N;++i)
	{
		if(A[i] / V < B[i])
		{
			return false;
		}
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	
	cin>>N;
	for(int i = 1;i <= N ;++i)
	{
		cin>> A[i] >> B[i];
	}
	int L = 1,R = 1000000000,V_min;//先找最小值 
	while(L <= R)
	{
		int mid = L + R >> 1;
		if(check_min(mid))//如果复符合要求 
		{
			V_min = mid;
			R = mid - 1;
		}
		else
		{
			L = mid + 1;
		}
	}
	L = 1, R = 1000000000;
	int V_max;
	while(L <= R)
	{
		int mid = L + R >> 1;
		if(check_max(mid))
		{
			V_max = mid;
			L = mid + 1;
		}
		else
		{
			R = mid - 1;
		}
	}
	cout<<V_min<<" "<<V_max<<endl;
	
	return 0;            
}
0 回复 0 转发 1 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!