二分查找和二分答案（基础）-海口c网

前言

二分的本质

二分的代码实现

二分查找

题目

洛谷 P1571 眼红的Medusa

洛谷 P1102 A-B 数对

洛谷 P1678 烦恼的高考志愿

OpenJudge 01：查找最接近的元素

二分答案

实现

题目

洛谷 P1824 进击的奶牛

洛谷 P1182 数列分段 Section ||

洛谷 P1281 书的复制

前言

前面的题比较简单，但看到最后有惊喜哦。

做题时先想暴力解，再优化，算法的目的是优化时间或空间或简化问题。

答案具有单调性，且能在O(n)时间内判定用二分优化。
暴力解是dfs求方案最值等，用动规优化，dfs本身就划分了阶段，参数可作为动规状态设计的参考
单调栈、堆等优化
线段树优化区间查询、求和等

二分的本质

二分是为了优化在一段具有单调性的区间里查找值的时间，时间复杂度O(log n)，每次查找确定区间的范围和区间的中间位置，查找的值和中间位置的值作比较，确定是哪个方向，来缩小区间。

能用二分的区间一定具有单调性，这样才能确定是去区间的左半段查找还是右半段查找。

二分查找是通过二分查找值，二分答案是通过二分确定结果（结果具有单调性），两者的思想相同，只是二分的应用不同。

二分的代码实现

1.区间定义（区间[L, R]中包含要查的值）：明确区间定义即可明确结束条件，明确区间如何缩小

2.结束条件：考虑即将结束时的区间和结果

3.结果：一般为L或mid

二分查找

二分的运用，一般是查找元素，要求区间必须有序。

题目

洛谷 P1571 眼红的Medusa

P1571 眼红的Medusa - 洛谷

先想暴力再想优化。耗时源是查找，用二分查找优化，先对b数组排序。

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;
const LL Maxm = 1e5 + 5;LL avct[Maxn], bvct[Maxm];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m;cin >> n >> m;for (LL i = 1; i <= n; ++i)  cin >> avct[i];for (LL i = 1; i <= m; ++i)  cin >> bvct[i];sort(bvct + 1, bvct + m + 1);LL L = 1, R = n, mid = 0;for (LL i = 1; i <= n; ++i) {L = 1, R = m;while (L <= R) {mid = L + ((R - L) >> 1);if (bvct[mid] < avct[i])  L = mid + 1;else if (bvct[mid] > avct[i])  R = mid - 1;else {cout << bvct[mid] << ' ';break;}}}return 0;
}

mid为结果，所以结束条件为L <= R，在L = R时再获取一次mid得到结果。

可用哈希解。

洛谷 P1102 A-B 数对

P1102 A-B 数对 - 洛谷

将A - B = C转化为A = B + C，B、C已知，二分查找数组中是否有B + C。

不会重复计算，A = B + C，但B ≠ A + C。

可用哈希解。

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 2e5 + 5;LL invt[Maxn], vct[Maxn], num[Maxn];LL f_search(LL x, LL n) {LL L = 1, R = n, mid = 0;while (L <= R) {mid = L + ((R - L) >> 1);if (vct[mid] < x)  L = mid + 1;else if (vct[mid] > x)  R = mid - 1;else  return mid;}return -1;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, c;cin >> n >> c;for (LL i = 1; i <= n; ++i) cin >> invt[i];sort(invt + 1, invt + n + 1);LL cnt = 0, idx = 0, res = 0;for (LL i = 1; i <= n; ++i) {if (invt[i] != invt[i - 1])  vct[++cnt] = invt[i];++num[cnt];}for (LL i = 1; i <= cnt; ++i) {idx = f_search(vct[i] + c, cnt);if (idx != -1) {res += num[i] * num[idx];}}cout << res;return 0;
}

洛谷 P1678 烦恼的高考志愿

P1678 烦恼的高考志愿 - 洛谷

设估分为x，估分最小相差值为w，则w = min(≤x的最大值，>=x的最小值)。二分查找。

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxm = 1e5 + 5;
const LL Maxn = 1e5 + 5;
const LL MVal = 1e14 + 5;LL vctm[Maxm], vctn[Maxn];// <= x的最大值
LL f_search1(LL x, LL m) {LL L = 1, R = m, mid = 0;while (L < R) {mid = L + ((R - L) >> 1) + 1;if (vctm[mid] <= x)  L = mid;else  R = mid - 1;}return vctm[L];
}// >= x的最小值
LL f_search2(LL x, LL m) {LL L = 1, R = m, mid = 0;while (L < R) {mid = L + ((R - L) >> 1);if (vctm[mid] < x)  L = mid + 1;else  R = mid;}return vctm[L];
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL m, n;cin >> m >> n;for (LL i = 1; i <= m; ++i)  cin >> vctm[i];for (LL i = 1; i <= n; ++i)  cin >> vctn[i];vctm[0] = -5, vctm[m + 1] = MVal;sort(vctm + 1, vctm + m + 1);LL res = 0;for (LL i = 1; i <= n; ++i) {res += min(abs(vctn[i] - f_search1(vctn[i], m)), abs(vctn[i] - f_search2(vctn[i], m)));}cout << res;return 0;
}

f_search1函数mid = (L + R + 1) / 2 = L + ((R - L) >> 1) + 1，当L + 1 = R vctm[mid] <= x时，若mid = (L + R) / 2 = L，L赋值为L，会死循环。

f_search2函数mid = (L + R) / 2 = L + ((R - L) >> 1)，当L + 1 = R vctm[mid] <= x时，若mid = (L + R) / 2 + 1 = R，L赋值为R + 1，区间外不是结果。

OpenJudge 01：查找最接近的元素

OpenJudge - 01:查找最接近的元素

代码如下：

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;
const LL MVal = 1e14;LL vct[Maxn];// <= x 的最大值
LL f_search1(LL x, LL n) {LL L = 1, R = n, mid = 0;while (L < R) {mid = L + ((R - L) >> 1) + 1;if (vct[mid] > x)  R = mid - 1;else  L = mid;}return vct[L];
}// >= x的最小值
LL f_search2(LL x, LL n) {LL L = 1, R = n, mid = 0;while (L < R) {mid = L + ((R - L) >> 1);if (vct[mid] < x)  L = mid + 1;else  R = mid;}return vct[L];
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, num, res1, res2;cin >> n;for (LL i = 1; i <= n; ++i)  cin >> vct[i];vct[0] = -5, vct[n + 1] = MVal;cin >> m;while (m--) {cin >> num;res1 = f_search1(num, n);res2 = f_search2(num, n);if (abs(num - res1) > abs(num - res2))  cout << res2 << '\n';else  cout << res1 << '\n';}return 0;
}

二分答案

二分的运用，最优解问题可抽象为函数，函数的“定义域”为方案，“值域”为最优解（结果）。设S为结果，结果越大越优，对于任意x > S的x不是结果，否则和S为最优解条件冲突，任意x < s不是最优解，S位于一个分界线上，具有单调性，可用二分+判定得到结果。

判定函数必须能在O(n)时间内判定，否则用二分的效率约等于暴力。

实现

1.最优解：明确如何二分

2.写出二分：整体框架

3.判定函数：判定给的值是否可行，确定区间如何缩小。一般用贪心实现，最贪了可行，说明可行，最贪了不可行，说明无论如何不可行。

题目

洛谷 P1824 进击的奶牛

P1824 进击的奶牛 - 洛谷

最优解：最大的最近距离，满足单调性

二分：if的区间调整是L = mid，mid可能是结果。

判定函数：设给定值为x，贪心，每个牛的间隔是>=x的最小值（最优策略），统计可放下几头牛，return 放的牛数 >= C，需用pre记录前一个牛所在的隔间坐标，隔间坐标要排序。

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;LL vct[Maxn];bool f_check(LL num, LL n, LL c) {LL pre = vct[1], res = 1;for (LL i = 2; i <= n; ++i) {if (vct[i] - pre >= num) {++res;pre = vct[i];}}return res >= c;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, c;cin >> n >> c;for (LL i = 1; i <= n; ++i)  cin >> vct[i];sort(vct + 1, vct + n + 1);LL L = 1, R = vct[n] - vct[1], mid = 0;while (L < R) {mid = L + ((R - L) >> 1) + 1;if (f_check(mid, n, c) != false)  L = mid;else  R = mid - 1;}cout << L << '\n';return 0;
}

洛谷 P1182 数列分段 Section ||

P1182 数列分段 Section II - 洛谷

最优解：每段和最大值最小

判定函数：贪心，设给定的参数（每段和最大值）为x，vct为前缀和，sum为这段之前的段的和。若vct[i] - sum > x，将i分配到下一段，++cnt，统计可尽可能少的分为几段，设分的段数为cnt，若cnt < m，说明若分成m段，每段和最大值 <= x，若cnt = m，说明分成m段，每段和最大值 = x。

举一反三：若段不是连续的，就……

#include <iostream>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;LL vct[Maxn];bool f_check(LL x, LL n, LL m) {LL cnt = 1, sum = 0;for (LL i = 1; i <= n; ++i) {if (vct[i] - sum > x) {sum = vct[i - 1];++cnt;}}return cnt <= m;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, mVal = 0;cin >> n >> m;for (LL i = 1; i <= n; ++i) {cin >> vct[i];mVal = max(mVal, vct[i]);vct[i] += vct[i - 1];}LL L = mVal, R = vct[n], mid = 0;while (L < R) {mid = L + ((R - L) >> 1);if (f_check(mid, n, m) != false)  R = mid;else  L = mid + 1;}cout << L << '\n';return 0;
}

洛谷 P1281 书的复制

P1281 书的复制 - 洛谷

最优解：每个人抄写的书是连续的且每个人至少抄一本书，抄写页数最多的人的抄写页数，可用二分

判定函数：类似上一题，但倒着遍历，因为要求前面的人少写。

求结果：要获取具体的方案，L为最少的抄写页数最多的人的抄写页数，倒着遍历，idx记录当前人的终止编号，初始为m，若vct[i] - sum > L，则说明前面为一个人的抄写，push_back进result，idx = i，最后还要push_back一下，倒着输出result即为答案，每个人都有活可干，所以result.size() 等于k。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxm = 500 + 5;LL vct[Maxm];
vector<pair<LL, LL> > result;void getRes(LL x, LL m, LL k) {LL cnt = 1, sum = 0, idx = m;result.clear();for (LL i = m; i >= 1; --i) {if (vct[i] - sum > x) {sum = vct[i + 1];++cnt;result.push_back({i + 1, idx});idx = i;}}result.push_back({1, idx});
}bool f_check(LL x, LL m, LL k) {LL cnt = 1, sum = 0;for (LL i = m; i >= 1; --i) {if (vct[i] - sum > x) {sum = vct[i + 1];++cnt;}}return cnt <= k;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL m, k, mVal = 0;cin >> m >> k;for (LL i = 1; i <= m; ++i) {cin >> vct[i];mVal = max(vct[i], mVal);}for (LL i = m - 1; i >= 1; --i)  vct[i] += vct[i + 1];LL L = mVal, R = vct[1], mid = 0;while (L < R) {mid = L + ((R - L) >> 1);if (f_check(mid, m, k) != false)  R = mid;else  L = mid + 1;}getRes(L, m, k);for (LL i = result.size() - 1; i >= 0; --i)  cout << result[i].first << ' ' << result[i].second << '\n';return 0;
}

测试点情况如下：