二分典型例题
备战蓝桥杯系列全部文章
分享看过的高赞的文章，有助于你对于二分的理解
巨人的肩膀：
给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。
对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 nn 和 qq，表示数组长度和询问个数。
第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。
输出格式
共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
本题目是二分的模板题目，但是难点就是对于边界的处理，究竟是大于等于还是大于呢？这时候left，right，mid的关系是怎么样的呢，个人还是比较推荐首先判断没有等于的情况。举栗子来说11111111122255566
你要找2， 此时如果你的a[mid] 小于2,那么这时候边界很明确（一定是在这个mid值的右边，不包括mid），left肯定是mid+1的。然后判断a[mid]>=2,right是可以取到mid值的，所以right=mid
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n, q, k;
cin >> n >> q;
for (int i = 0; i < n; i ++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < q; i ++) {
cin >> k;
int left = 0, right = n - 1;
while (left < right) {
int mid = left + right >> 1; //left = mid + 1 ,mid 就不需要再次加1了
if (a[mid] >= k) {
right = mid;
}else {
left = mid + 1; //a[mid] 小于 k 那么left = mid + 1
}
}
if (a[right] == k) {
cout << right << ' ';
right = n - 1;
while (left < right) {
int mid = left + right + 1 >> 1;
if (a[mid] <= k) {
left = mid;
}else {
right = mid - 1;
}
}
if (a[left] == k) {
cout << left;
}
}else {
cout << "-1 -1";
}
cout << endl;
}
}
给定一个浮点数 nn，求它的三次方根。
输入格式
共一行，包含一个浮点数 nn。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 66 位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000
对于实数来说，我们left 与 right的移动幅度不是单纯的+1 -1 ，因此我们循环的判断条件不再只是right > left
变成了right - left > 1e-8 题目要求精度为1e-6
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
double n;
cin >> n;
double left = -10000, right = 10000;
while (right - left > 1e-8) { //right - left 在10^(-8)次方的范围内，符合精度
double mid = (right + left) / 2;
if (mid * mid * mid <= n) {
left = mid;
}else {
right = mid;
}
}
printf("%.6lf", right);
return 0;
}
机器人正在玩一个古老的基于 DOS 的游戏。
游戏中有 N+1N+1 座建筑——从 00 到 NN 编号，从左到右排列。
编号为 00 的建筑高度为 00 个单位，编号为 ii 的建筑高度为 H(i)H(i) 个单位。
起初，机器人在编号为 00 的建筑处。
每一步，它跳到下一个（右边）建筑。
假设机器人在第 kk 个建筑，且它现在的能量值是 EE，下一步它将跳到第 k+1k+1 个建筑。
如果 H(k+1)>EH(k+1)>E，那么机器人就失去 H(k+1)−EH(k+1)−E 的能量值，否则它将得到 E−H(k+1)E−H(k+1) 的能量值。
游戏目标是到达第 NN 个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
输入格式
第一行输入整数 NN。
第二行是 NN 个空格分隔的整数，H(1),H(2),…,H(N)H(1),H(2),…,H(N) 代表建筑物的高度。
输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。
数据范围
1≤N,H(i)≤1051≤N,H(i)≤105,
输入样例1：
5
3 4 3 2 4
输出样例1：
4
输入样例2：
3
4 4 4
输出样例2：
4
输入样例3：
3
1 6 4
输出样例3：
3
二分的做法：
题目分析，如果当前的能量是高于H[i]的那么最终的能量加上他们的差值，如果是小于h[i]的，就减去差值。最终整理式子可以得出来cur = cur * 2 - h[i]
如果当前的cur 能够满足题意，那么所有的大于cur的值都是可以满足这个题意的，因此我们可以用二分的方式计算得出最小的满足题意的值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
bool check(int x) {
//判断是否成立 保证每一次的结果2 * curvalue - next >= 0
int cur = x;
for (int i = 1; i <= n; i++) {
cur = 2 * cur - a[i];
if (cur > 1e5) return true;
if (cur < 0) return false;
}
return true;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++ ) cin >> a[i];
int l = 0, r = 100000;
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid; //如果mid是可以的 mid的右边都是可以的，右边界变为mid
}else {
l = mid + 1;
}
}
cout << l;
}
贪心的做法：
我们想让机器人满足题目的意思，并且高度最小，我们可以从末尾开始向前进行层层递推，让末尾为0
上面我们推断出的式子是next = cur * 2 - h[i]
因此从后向前推断 x = (x + h[i]) / 2
注意进位的问题
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int fins = 0;
for (int i = n - 1; i >= 0; i--) {
if ((a[i] + fins) % 2 == 0) {
fins = (a[i] + fins) / 2 ;
}else {
fins = (a[i] + fins + 1) / 2;
}
}
cout << fins;
}
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 44 个正整数的平方和。
如果把 00 包括进去，就正好可以表示为 44 个数的平方和。
比如：
5=02+02+12+225=02+02+12+22
7=12+12+12+227=12+12+12+22
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 44 个数排序：
0≤a≤b≤c≤d0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,da,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 NN。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5∗1060<N<5∗106
输入样例：
5
输出样例：
0 0 1 2
暴力杯，你值得拥有
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=2500010;
int n;
int main()
{
cin>>n;
for(int a=0;a*a<=n;a++)
{
for(int b=a;a*a+b*b<=n;b++)
{
for(int c=b;a*a+b*b+c*c<=n;c++)
{
int t=n-a*a-b*b-c*c;//存一下
int d=sqrt(t);
if(d*d==t)//等于就相当于找到了一组解
{
printf("%d %d %d %d\n",a,b,c,d);
return 0;
}
}
}
}
}
手写哈希数组
枚举c与d将得到的值都存放在C与D的数组中去，
然后枚举a与b 判断n - a * a - b *b是否在哈希表中存在，如果存在就得到解了
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5500010;
int C[N], D[N];
int n;
int main()
{
memset(C , -1, sizeof C);
cin >> n;
//将c * c + d * d的所有的结果存放到C与D数组中
for (int c = 0; c * c <= n; c++)
for (int d = c; d * d + c * c <= n; d++)
{
int t = c * c + d * d;
if (C[t] == -1) //如果没有遇见过就存放到C与D数组中，如果存在过也不在替换了，因为要保证是最小的
{
C[t] = c;
D[t] = d;
}
}
for (int a = 0; a * a <= n; a++)
for (int b = a; a * a + b * b <= n; b++)
{
int t = n - a * a - b * b; //枚举a和b，得到的值查看手写的哈希表中是否出现
if (C[t] != -1)
{
cout << a <<" " << b << " "<< C[t] <<" " << D[t];
return 0;
}
}
return 0;
}
二分的做法
其实跟哈希的思想是差不多的，将枚举的c与d的结果s， c， d都放进结构体数组sum中
然后根据枚举a b得到的数对sum数组进行二分查找
我们可以看到，二分的效率肯定是不如上面的哈希的，但是重在过程的理解嘛
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2500010;
struct Sum
{
int s, c, d;
bool operator < (const Sum& a){ //我们排序是优先根据s排序，对结构体排序所以重载小于号
if(s != a.s)return s < a.s;
if(c != a.c)return c < a.c;
if(d != a.d)return d < a.d;
}
}sum[N];
int m,n;
int main()
{
cin >> n;
for (int c = 0; c * c <= n; c++)
for (int d = c; d * d + c * c <= n; d++)
{
int t = c * c + d * d;
sum[m++] = {t, c, d}; //将枚举得到的t c d都放进sum中去
}
sort(sum, sum + m);
for (int a = 0; a * a <= n; a++)
for (int b = 0; b * b + a * a <= n; b++)
{
int t = n - a * a - b * b;
int l = 0, r = m - 1;
//开始查找s等于t的存在于数组中最左边的值
while (l < r){
int mid = l + r >> 1;
if (sum[mid].s >= t) {
r = mid;
}else {
l = mid + 1;
}
}
if (sum[l].s == t) { //最终判断一下是不是
cout << a << " " << b <<" " << sum[l].c << " " << sum[l].d ;
return 0;
}
}
}
33. 搜索旋转排序数组（link）
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4-
nums 中的每个值都 独一无二
- 题目数据保证
nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
分析如下：本题目中原本的顺序是完全升序的，经过旋转之后左边和右边都是有序的，并且左边最小值nums[0] 也是 大于右边的
最大值nums[n - 1]的，因此我们可以判断一下mid所处于哪一个范围从而进行二分查找
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
cout << n <<" ";
if (!n) return -1;
if (n == 1) return nums[0] == target ? 0 : -1;
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
//开始进行多种情况的分析
//如果mid是在左边的那一趴
if (nums[mid] >= nums[0]) {
//确定target在0 - mid
if (target >= nums[0] && target < nums[mid]) {
r = mid - 1; //因为早就判断nums【mid】不是了，因此都是mid + - 1
}else {
l = mid + 1;
}
}else{ //在右边的那一趴
if (target > nums[mid] && target <= nums[n -1]) {
l = mid + 1;
}else {
r = mid -1;
}
}
}
return -1;
}
};
儿童节那天有 KK 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NN 块巧克力，其中第 ii 块是 Hi×WiHi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 NN 块巧克力中切出 KK 块巧克力分给小朋友们。
切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
例如一块 6×56×5 的巧克力可以切出 66 块 2×22×2 的巧克力或者 22 块 3×33×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 NN 和 KK。
以下 NN 行每行包含两个整数 HiHi 和 WiWi。
输入保证每位小朋友至少能获得一块 1×11×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤1051≤N,K≤105,
1≤Hi,Wi≤1051≤Hi,Wi≤105
输入样例：
2 10
6 5
5 6
输出样例：
2
分析：我们遇见这种题目的时候就要想一下如果二分查找答案能否是可行的，就要有一个check函数判断你二分的答案是否是可行的，根据题目的简单分析我们发现可以用check函数直接判断一个答案是否是可行的，那问题就简单了，直接二分查找就行了
二分的边界问题：假设cur为现在判断的值,如果cur是可行的 那么小于cur的值都是可以至少分成k份，但是不一定分的饼干边是最
长的，因此左边界left = mid
如果cur不足以分成k分，那么就是边太大了，右边界right = mid -1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], w[N];
int n, k;
bool check(int x)
{
int sum = 0;
for (int i = 0; i < n; i++) {
sum += (h[i] / x) * (w[i] / x);
if (sum >= k) return true;
}
return false;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> h[i] >> w[i];
int l = 1, r = N;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) {
l = mid;
}else {
r = mid - 1;
}
}
cout << l;
return 0;
}
最后，希望大家在蓝桥杯取得好成绩！
