二分答案（定义，做法，最短子序列问题，力扣分享巧克力，洛谷P2678 [NOIP2015 提高组] 跳石头，atcoder D - Widespread，牛客小黑月赛37 I-加减）

目录

二分答案

定义

做法

最短子序列问题

解题思路：

力扣 分享巧克力

解题思路：

结论：

洛谷P2678 [NOIP2015 提高组] 跳石头

解题思路：

atcoder D - Widespread

解题思路：

牛客小黑月赛37 I-加减

解题思路：

二分答案

定义

它是二分思想的一个进阶技巧。通过观察发现问题的答案存在单调性,通过二分答案后检查答案是否能够达到。

直观来讲，二分答案就是一种(因为答案有单调性，所以)利用二分思想优化枚举答案过程的算法

做法

1.发现答案的单调性

2.二分答案

3.检查答案是否可行（每道题的重点在这）

最短子序列问题

给定一个正整数序列,让你取一个子段，使得其区间的和大于等于$x$,问你这个子段最短可能长度是多少。

解题思路：

首先预处理前缀和（方便后面计算区间和），然后用二分的思想来找答案的长度，这道题的答案是最短子序列的长度，检查函数内，通过一个滑动窗口来选中mid个元素，每次保留最大值，原因是最大值最容易满足>=x，最后传回判断，再缩减左右端点，因为答案是越靠后越容易实现，所以此题为后缀模型，所以输出L

#include <iostream>
using namespace std;
int a[1005], s[1005] = {0}, n, x;int ok(int mid)
{int mx = 0;//i为答案的长度for(int i = mid; i <= n ; i++){//i-mid 与 i 之间构成了长度为 mid 的滑动窗口//每次求最大值，原因是最大值是最有可能满足>=x的mx = max(mx, s[i] - s[i - mid]);}//最后传回判断return mx >= x;
}int main()
{cin >> n >> x;//输入序列，预处理前缀和for(int i = 1; i <= n; i++){cin >> a[i];s[i] = s[i-1] + a[i];}int l = 1, r = n, mid;while(l <= r){mid = (l + r) >> 1;//cout << mid << " " << ok(mid) << endl;//用检查函数来判断更改哪个端点，如果判断函数传回满足，就缩减右端点//如果不满足就缩减左端点， 因为题目是给一个升序的序列，越往后越容易实现题目要求if(ok(mid))r = mid - 1;else l = mid + 1;}//此题为后缀模型，越往后越容易实现题目要求cout << l;return 0;
}

力扣 分享巧克力

解题思路：

#include <iostream>using namespace std;
int n, k, a[10005], maxn = 0;int ok(int mid)
{int o = 0, sum1 = 0;//从第一个位置开始累加for(int i = 1; i <= n; i++){sum1 += a[i];//当sum1满足了我们mid（枚举的甜度），那么就记一次数if(sum1 >= mid){sum1 = 0;o++;}}//最终要判断我们是否满足了题目要求分成k+1块，如果分的比k+1要多，对于我们答案来说是不影响的return o >= k + 1;
}int main()
{cin >> n >> k;for(int i = 1; i<= n; i++){cin >> a[i];//存下数组里面最甜的那一块if(maxn < a[i])maxn = a[i];}int l = 1, r = maxn;while(l <= r){int mid = (l + r) >> 1;//这是一个前缀模型，通过ok函数进行端点的变动if(ok(mid))l = mid + 1;else r = mid - 1;}cout << r;return 0;
}
/*
9 5
1 2 3 4 5 6 7 8 9
*/

结论：

求最小值的最大值是前缀模型

求最大值的最小值是后缀模型

洛谷P2678 [NOIP2015 提高组] 跳石头

题目链接：[NOIP2015 提高组] 跳石头 - 洛谷

解题思路：

答案是求最小值的最大值，而且答案一定是 1 <= ans <= l，所以我们很自然可以想到二分答案前缀和，因为越小越容易实现，然后我们通过OK函数来判断，mid当ans是否成立，在ok函数中，通过判断后一块与前一块的距离是否满足>=mid，不满足就撤一块，再用后一块与当前的前一块进行比较，所以加了一个变量q储存用来减去的石头，最后判断撤走的石头满不满足题目要求，最终输出R，因为是前缀模型

#include<bits/stdc++.h>
using namespace std;#define ll long long
const int maxn = 5e4 + 5;
int l, n, m;
int a[maxn] = {0};int ok(int mid)
{//cnt是撤走的石头数量，q是储存用于减去的石头的下标int cnt = 0, q = 0;//枚举每一块石头for(int i = 1; i <= n + 1; i++){//判断之间的距离满不满足>=mid，不满足就撤走一块石头，再进行判断if(a[i] - a[q] < mid){cnt++;}else{//满足条件就储存当前的下标，用于下一次比较q = i;}}//返回撤走的石头数是否满足题目要求return cnt <= m;
}int main()
{cin >> l >> n >> m;//输入石头距离for(int i = 1; i <= n; i++)cin >> a[i];//终点特殊处理a[n+1] = l;int le = 1, r = l;//二分答案while(le <= r){int mid = (le + r) >> 1;if(ok(mid))le = mid +1;else r = mid - 1;}//前缀模型输出Rcout << r;return 0;
}

atcoder D - Widespread

题目链接：D - Widespread

题目大意：给你n个正整数,你有一个操作是让一个数减A,然后让其他数减B.保证A > B问你最少多少次操作能够让所有数降到<=0

1≤N≤10^5

1 ≤ B < A ≤ 10^9

1 ≤ h_i ≤ 10^9

解题思路：

题目求操作，肯定是操作越多越容易实现，所以这是一个二分答案后缀模型，左右端点分别为2，1e9（假设所有数为1，假设B为1），用一个ok函数判断mid答案是否合法，在ok函数中判断当前的w[i]是否小于等于b*mid（答案数乘B），如果小于就不用消耗我们的次数（A-B的差值），如果大于的话我们就需要消耗mid次数（这里我用K来存），消耗完之后还要进行一次判断，因为第一次消耗可能是3/2=1，剩下还有一个1没消耗完，所以我们手动还要消耗一次，最后判断一下次数是否变为负数，如果变负数直接返回false，出了for循环就代表k>=0，返回true

这道题给我的教训就是，大数据一定要用long long，这道题为此浪费了半个多小时！！！

#include<bits/stdc++.h>
using namespace std;#define ll long long
const ll maxn = 1e5 + 5;
ll n, a, b;
ll w[maxn];int ok(ll mid)
{ll k = mid;//遍历所有元素for(ll i = 1; i <= n; i++){//如果小于mid答案*B就不处理if(w[i] <= b*mid)continue;//否则就消耗次数k -= (w[i]-b*mid) / (a-b);//如果碰到不整除的情况就需要手动加一次if((w[i]-b*mid) - (w[i]-b*mid)/(a-b)*(a-b) > 0)k -= 1;//次数如果变为负数就返回falseif(k < 0)return 0;}//出了循环就代表k>=0return 1;
}int main()
{cin >> n >> a >> b;for(int i = 1; i <= n; i++)cin >> w[i];//假设所有数为1，假设B为1,左右端点ll l = 1, r = 1e9;while(l <= r){int mid = (l + r) >> 1;//检查答案是否合法if(ok(mid))r = mid - 1;else l = mid +1;}//这是一个二分答案后缀模型cout << l;return 0;
}

牛客小黑月赛37 I-加减

题目链接：牛客小黑月赛37 I-加减

解题思路：

题目要求出现最多元素的次数，我们自然想到二分答案前缀模型，因为满足<=k，答案越小越容易实现，开始我们做一个前缀和处理，方便后面通过中位数来加消耗的次数（就不用写绝对值来求次数了），进入OK函数，因为我们L和R枚举的是出现的次数，所以我们用一个滑动窗口来从开头往后遍历，判断次数是否小于K（我们先mid*（mid到左边下标-1）的个数，然后减去这一段的和，因为是排好序的，所以求出来就是需要加1的操作次数，第二部分，我们用（右下标的前缀和-mid位置的前缀和），得到的就是右下标到mid+1位置的这一段，因为是排好序的，所以这一段都比mid大，所以要对这些原素做-1操作，所以这些也加入操作数），跳出循环后就一定>k所以返回false

#include<bits/stdc++.h>
using namespace std;#define ll long long
const ll maxn = 1e5 + 5;
ll a[maxn];
ll sum1[maxn];
ll n, k;ll ok(ll mid)
{//做一个滑动窗口for(ll i = 1; i+mid-1 <= n; i++){//求出中位数ll midd = (i + i + mid - 1) >> 1;//见代码加粗部分if(a[midd]*(midd-i+1)-(sum1[midd]-sum1[i-1])+(sum1[i+mid-1]-sum1[midd])-a[midd]*(i+mid-1-midd) <= k)return true;}return false;
}int main()
{cin >> n >> k;for(int i = 1; i <= n; i++)cin >> a[i];//排序，这样在后续可以通过中位数来求sort(a+1, a+n+1);for(int i = 1; i <= n; i++)sum1[i] = sum1[i-1] + a[i];//枚举出现元素次数的最小最大可能，用二分优化ll l = 1, r = n;while(l <= r){ll mid = (l + r) >> 1;if(ok(mid))l = mid + 1;else r = mid -1;}cout << r;return 0;
}