常见的二分类型:
1. 整数二分
2. 小数二分(相对较少)
3. 二分答案(最常见)
二分最直接的思想就是用O(logn)的时间较快的在数组中找见想要找的边界数,枚举时间较慢O(n)。 小数二分与整数二分的思想相一致,就不在赘述了。
☆ 理解二分一定要理解的问题是答案取得是区间的右边界,则返回的是l,取区间的左边界,则返回的是r,下面用一张图来详细讲解。
整数二分的模版:
//找到升序数组a中的第一次出现的位置
int l = 0, r = 1e9;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while (l + 1 != r) {
int mid = (l + r) >> 1;//l,r相邻退出
//如果a为升序,说明mid偏大了,需要减小mid,将r变小
if (a[mid] >= x) r = mid;
else l = mid;
}
cout << r << '\n';
下面就是一道经典的整数二分
#include <bits/stdc++.h>
using namespace std;
int main() {
int data[200];
for (int i = 0; i <200; i ++) data[i] = 4 * i + 6;
int l = -1, r = 199;
int x;cin >> x;
while (l + 1 != r) {
int mid = (l + r) >> 1;
if (data[mid] >= x) r = mid;
else l = mid;
}
cout << r;
}
二分答案的核心语句:
if (check(mid) >= m ) l = mid;
else r = mid;
check()函数的编写,我的做法是:
先遍历一遍题目中的数组,然后定义一个lst表示上一个数求出两者之间的差值,最后判断这个数值与体重条件的关系,最后返回与check函数值相比将的值。
这里问题的关键就在于理解距离和岩石数的转换以及mid和check所表示的是什么,最短的跳跃距离正相关于至多移走的岩石数,移走的岩石数越多,最短距离越大,mid表示的是两个相邻之间的距离,check记录的则是移走的岩石的数量,当两块石头中间的距离不够mid的时候,去掉后一块石头,特例判断就是最后一块石头不能去掉。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e4 +9;
int a[N], L, n, m;
int check(int mid) {
int res = 0, lst = 0;//lst表示上一块岩石
for (int i = 1; i <= n; i++) {
if (a[i] - a[lst] < mid)
{
res ++;
continue;
}
lst = i;
}
if (L - a[lst] < mid) return m + 1;
return res;
}
int main() {
cin >> L >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
ll l = 0, r = 1e9;
while (l + 1 != r) {
int mid = (l + r) >> 1;
if (check(mid) <= m) l = mid;
else r = mid;
}
cout << l;
return 0;
}
很明显这题中的两个数值的转换是负相关的,解题的过程中要注意的是输入的数组不一定是有序的,要排序。check里要判断lst是存在的。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a[N];
int n, m;
int check(int mid) {
int lst = 0,res = 0;
for (int i = 1; i <= n; i++) {
if (lst && a[i] - a[lst] < mid) continue;
res ++;
lst = i;
}
return res;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >>a[i];
sort(a +1, a + 1 + n);
int l = 0, r = 1e9;
while (l + 1 != r) {
int mid = (l + r) >> 1;
if (check(mid) >= m) l = mid;
else r = mid;
}
cout << l;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, k;
ll check(ll mid) {
ll res = 0;
for (int i = 1; i <= n; i++) res += min(m, mid /i);
return res;
}
int main()
{
cin >> n >> m >> k;
ll l = 0, r = 1e14;
while (l + 1 != r) {
ll mid = (l + r) >> 1;
if (check(mid) >= k) r = mid;
else l = mid;
}
cout << r;
return 0;
}
标签:二分,int,ll,mid,C++,答案,using,check
From: https://blog.csdn.net/lly18435759909/article/details/136632701