1.两段二分
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
const int N = 10010;
int n;
pii a[N];
bool check_1(int mid)
{
for (int i = 1; i <= n; i ++)
if (a[i].x / mid > a[i].y) return false;
return true;
}
bool check_2(int mid)
{
for (int i = 1; i <= n; i ++)
if (a[i].x / mid < a[i].y) return false;
return true;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
int l = 1, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
//二分的是此时vmin产生的bi>题给bi,则vmin在绿左端点,v再小就>bi了
if (check_1(mid)) r = mid;
else l = mid + 1;
}
cout << l << ' ';//vmin不应该是红右端点?
r = 1e9;
while (l < r)
{
int mid = l + r + 1 >> 1;
//二分的是此时mid产生的<bi,vmax为红右端点,v再大就<bi了
if (check_2(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
return 0;
}
2.优化版二分 看y总视频讲解
注意:
·r=1e9+1,是因为题目给的b的范围是1e9,但我们二分找答案的函数传的是b-1来代表题目传的b,当题中输入的b为1时,二分函数参数中b-1=0。
即我们实际求二分包含了b=0的情况,因此需要包含r=1e9+1(应该>1e9就行)使得v有可能取得r,从而b=0的情况
·二分时二段性的条件灵活找,只要能使得答案在边界就行,比如此题y总直接转化为了b-1的情况。
3.理解整除含义
1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int v_min = 1, v_max = 1e9;
while (n -- )
{
int a, b;
scanf("%d%d", &a, &b);
v_min = max(v_min, a / (b + 1) + 1);
v_max = min(v_max, a / b);
}
printf("%d %d\n", v_min, v_max);
return 0;
}