二分三分+例题

1.二分模板

后继：

int l = 0, r = n - 1, mid;//后继while (l < r){mid = (l + r) >> 1;if (q[mid] >= x) r = mid;else l = mid + 1;}//前驱int l = 0, r = n - 1, mid;while (l < r){mid = (l + r + 1) >> 1;if (q[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;}

2.关于二分的stl

返回的是地址，不是那个要查找的数的下标。所以就注定了在这个函数的后边就要减去这个数组的首地址，即这个数组的数组名。只有这样才代表那个要查找的数字的下标

a.binary_search：查找某个元素是否出现。

a.函数模板：binary_search(arr[],arr[]+size , indx)

b.参数说明：
    arr[]：数组首地址
    size：数组元素个数
    indx:需要查找的值

c.函数功能：在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到indx元素则真，若查找不到则返回值为假。

3.二分习题

1.序列划分

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
int n, m;
int a[maxn];
int check(int x) {int cut = 1;int s = a[1];for (int i = 2; i <= n; i++) {if (s + a[i] <= x) s += a[i];else { s = a[i]; cut++; }}return cut;
}
int bin_search(int l, int r) {while (l < r) {int mid = l + (r - l) / 2;if (check(mid) <= m) {r = mid;}else {l = mid + 1;}}return l;
}
int main() {int t;ll mx, sum;cin >> t;while (t--) {mx = 0, sum = 0;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];sum += a[i];if (mx < a[i])mx = a[i];}int ans = bin_search(mx, sum);cout << ans;}return 0;
}

2.数的范围

活动 - AcWing

#include <iostream>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;const int N = 100010;int n, m;
int q[N];int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) scanf("%d", &q[i]);while (m--){int x;scanf("%d", &x);int l = 0, r = n - 1, mid;while (l < r){mid = (l + r) >> 1;if (q[mid] >= x) r = mid;else l = mid + 1;}if (q[l] != x) cout << "-1 -1" << endl;else{cout << l << " ";int l = 0, r = n - 1, mid;while (l < r){mid = (l + r + 1) >> 1;if (q[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;}}return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,q,k,x1,x2,t;
int a[100010];
int main(){cin >> n >> q;for(int i = 0;i < n;i++){cin >> a[i];}while(q--){cin >> k;x1 = lower_bound(a,a + n,k) - a;x2 = upper_bound(a,a + n,k) - a - 1;if(x1 == x2 + 1)cout << -1 << ' ' << -1 << endl;else cout << x1 << ' '<< x2 << endl;}return 0;
}

3.进击的奶牛

进击的奶牛 - 洛谷

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int a[N];
int n,c;bool check(int dis){int cnt=1,place=0;for(int i=1;i<n;i++){if(a[i]-a[place]>=dis){cnt++;place=i;}}if(cnt>=c) return true;else return false;
}
int main(){scanf("%d%d",&n, &c);for(int i=0;i<n;i++) scanf("%d",&a[i]);sort(a,a+n);int l=0,r=a[n-1]-a[0];int ans=0;while(l<r){int mid=l+(r-l)/2;if(check(mid)){ans=mid;l=mid+1;}else{r=mid;}}cout<<ans;return 0;
}

4.（实数二分）浮点数的三次方根

注：这里使用 1e10-8，是因为题目要求保留小数点后6位，如果使用1e10-7, 那么这个因为四舍五入第八位到第七位，已经产生误差，输出六位时候误差会积累。如果使用-8，那么四舍五入第九位到第八位，取前六位时候，第七位会被truncate掉，但是第七位是准确值。

 #include <iostream>using namespace std;int main(){double n;cin>>n;double l=-10000,r=10000;while(r-l>1e-8){double mid=(l+r)/2;if(mid*mid*mid>=n) r=mid;else l=mid;}printf("%lf",l);return 0;}

5.用二分法求根号

#include <iostream>#define _CRT_SECURE_NO_WARNINGSusing namespace std;#include <math.h>int main(){double n;cin >> n;double l = -10000, r = 10000;while (r - l > 1e-8){double mid = (r + l)/2;if (mid*mid>n) r = mid;else l = mid;}cout << l;return 0;}

6.（实数二分&最大化最小值）
问题描述：主人过生日，m个人来庆生，有n块半径不同的圆形蛋糕，由m十1个人 (加上主人)分，要求每人的蛋糕必须一样重，而且是一整块（不能是几个蛋糕碎块，也就是说，每个人的蛋糕都是从一块圆蛋糕中切下来的完整一块)。问每个人能分到的最大蛋糕多大。

3122 -- Pie