[蓝桥杯]真题讲解：冶炼金属（暴力+二分）

一、视频讲解

视频讲解

二、暴力代码

//暴力代码
#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e4 + 10;void solve()
{int n; cin >> n;vector<int>a(n), b(n);//创建数组for(int i = 0; i < n; i ++)cin >> a[i] >> b[i];for(int i = 1; i <= 1e6; i ++)//枚举的转化率V{bool flag = true;//标记一下当前的V是否合法for(int j = 0; j < n; j ++){if(b[j] != (a[j] / i)){flag = false;break;}}if(flag){cout << i << " ";break;}}for(int i = 1e6; i >= 1; i --){bool flag = true;for(int j = 0; j < n; j ++){if(b[j] != (a[j] / i)){flag = false;break;}}if(flag){cout << i << " ";break;}}}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;//cin >> t;while(t--)solve();
}

三、正解代码

//冶炼金属：二分
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10;
int a[N], b[N];
int n;bool check_min(int mid)
{for(int i = 0; i < n; i ++){if(b[i] < a[i] / mid)return false;}return true;
}bool check_max(int mid)
{for(int i = 0; i < n; i ++)if(b[i] > a[i] / mid)return false;return true;
}void solve()
{cin >> n;for(int i = 0; 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;elselmin = mid + 1;}//求最大值。int lmax = 1, rmax = 1e9;while(lmax < rmax){int mid = lmax + rmax + 1 >> 1;if(check_max(mid))lmax = mid;elsermax = mid - 1;}cout << lmin << " " << lmax << endl;
}signed main()
{ios::sync_with_stdio(0);int t = 1;// cin >> t;while(t--)solve();
}