AcWing 4956. 冶炼金属

2024-03-12 00:04

文章标签 acwing 金属冶炼 4956

本文主要是介绍AcWing 4956. 冶炼金属，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于这个题，V越大，除出来的数就越小，V越小，除出来的数就越大，当我们找一个最大和最小值的时候，就可以通过这个性质进行二分来求解。

可以通过求满足 $[\frac{A}{V}]$ 小于等于 $B$ 的最小的 $V$ 来求最小值，通过满足 $[\frac{A}{V}]$ 小于等于 $B - 1$ 的 $V$ 最小的值来求最大值（这里是根据下取整函数的性质来决定的，取整函数的函数图像是一段段的横线，可以观察得B的V的最大值就是B-1的V的最小值）。

代码1：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;int get(int a, int b) {//二分函数//b最小取1，但是下面调用函数时有b-1，所以b有可能取到0，那么r就要取到比1e9大//则定义r为1e9+1int l = 1, r = 1e9 + 1;while (l < r) {int mid = l + r >> 1;if (a / mid <= b)r = mid;else l = mid + 1;}return r;
}int main() {int n; cin >> n;//最小一定是1，最大只能取1e9，大于1e9时B会得到0，不满足题目条件int minV = 1, maxV = 1e9;while (n--) {int a, b; cin >> a >> b;minV = max(minV, get(a,b));maxV = min(maxV, get(a, b - 1) - 1);}cout << minV << " " << maxV;return 0;
}

另一种二分法：
当我们要求V的最小值的时候，先浮现出一个数轴

|----------------------|----------------------|
L					  mid					  R

因为这里是找数，所以不是之前的那些需要满足条件，这里只需要看大小关系。
如果 $[\frac{A}{mid}]$ 大于B，就说明mid取小了，所以就要往右边找，也就是从mid +1 ~ R找，如果小于B，那就要从L ~ mid找。

对于求最大值也是同理。

另一种代码：非常模板风味的二分代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10;int n;
int a[N], b[N];bool check1(int mid) {  //check1求最小值用for (int i = 0; i < n; i++) {if (a[i] / mid > b[i])return false;     }return true;
}bool check2(int mid) {  //check2求最大值用for (int i = 0; i < n; i++) {if (a[i] / mid < b[i])return false;}return true;
}int main() {cin >> 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 (check1(mid))r = mid;else l = mid + 1;}cout << r << " ";//求最大值l = 1, r = 1e9;while (l < r) {int mid = l + r + 1 >> 1;if (check2(mid)) l = mid;else r = mid - 1;}cout << r << endl;return 0;
}