个人博客更好的阅读体验 请点击
好理解的二分方法
如果二分基本知识不牢的话,推荐看这篇博客 https://blog.csdn.net/raelum/article/details/128687109
二分实质是将准备求的边界 划分为两个对立的区间
由于转换率 V的取值一定是小于普通金属的数目A的,由题$1≤B≤A≤10^9$ 所以我们将V的取值范围也设在$1≤V≤10^9$ 这就是我们所要二分的边界
这里也有个要注意的点用SL的check(mid)举例
由于有n个A和B,我们要在每一个a[i].first / mid <= a[i].second 都判断成功时, 才能输出true,这样写起来很麻烦
所以我们将判断条件反着写,一旦a[i].first / mid <= a[i].second不成立,就判断为false
也就是只要a[i].first / mid > a[i].second 就为false,当循环内都不满足 才输出true
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
typedef pair<int, int> PII;
int n;
PII a[N];
bool check_1(int mid) //SL的判断条件
{
for (int i = 0; i < n; i ++ )
if(a[i].first / mid > a[i].second) return false;
return true;
}
bool check_2(int mid) //RL的判断条件
{
for (int i = 0; i < n; i ++ )
if(a[i].first / mid < a[i].second) return false;
return true;
}
int SL(int l, int r) //求左边界
{
while (l < r)
{
int mid = l + r >> 1;
if(check_1(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int RL(int l, int r) //求右边界
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if(check_2(mid)) l = mid;
else r = mid - 1;
}
return l;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i].first, &a[i].second);
int l = 1, r = 1e9; //因为这里写成int l = 0, r = 1e9; debug了两个小时!
printf("%d ", SL(l, r));
r = 1e9; //求出左边界后,我们求右边界时就可以从求出的左边界到1e9来查找右边界
printf("%d\n", RL(l, r));
return 0;
}
这里最开始写成int l = 0, r = 1e9; debug了两个小时!
原因:因为l~r这个区间是用来求除数V的,当l可以取0时,我们就有概率赋值到 l + r = mid=0这个值
在check函数内,a[i].first / mid,mid = 0, 除数就是0,当除数为0会形成Float Point Exception错误
然后测试的最后一组数据非常地恶心,左右边界都是1 1,所以当我们求左边界时,初始值mid = l + r >> 1,会一直满足check_1(mid),r = mid 一直进行,l + r >> 1 一直进行
最终mid = 1时,check_1(mid)成立, r = mid = 1,下一次循环mid = l + r >> 2 就等于0了(向下取整)
于是在check_1(mid)就会发生Float Point Exception错误 所以一定要注意边界问题!
实际上是审题不清
写的好
谢谢😋