OI笔记 | 二分与双指针优化
二分法
二分查找
二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
用$O(\log N)$的复杂度查找一个元素是否在有序数组中：
int a[MAX_N];
bool binarySearch(int l, int r, int x);
while(l <= r) {
int mid = (l + r) / 2;
if(x < a[mid]) r = mid - 1;
if(x > a[mid]) l = mid + 1;
if(x == a[mid]) return true;
}
return false;
自己写lower_bound类似算法的模板(注意到用STL的lower_bound时数组也要有序)：
int _lower_bound(int l = 0, int r = n + 1, int x) {
while(l < r - 1) {
int mid = (l + r) >> 1;
if(a[mid] < x) l = mid;
else r = mid;
}
return r;
}
例题 一元三次方程求解
有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。
题解
由于根与根之间距离大于$1$，我们只需枚举每一个长度为$1$的区间，再根据零点存在性定理（若$f(x_1)\times f(x_2)<0$则$\exists x_0 \in (x_1, x_2), f(x_0) = 0$.）用二分查找来找到确定的值。
#include <bits/stdc++.h>
using namespace std;
double a, b, c, d;
inline double f(double x) {
return (a * x * x * x + b * x * x + c * x + d);
}
int main() {
cin >> a >> b >> c >> d;
for(int i = -99; i <= 100; i++) {
if(f(i) == 0) printf("%d.00 ", i);
else if(f(i) * f(i - 1) < 0) {
double l = i - 1, r = i;
while(r - l >= 0.001) {
double mid = (l + r) >> 1;
if(f(mid) * f(l) < 0) r = mid;
else l = mid;
}
printf("%.2lf ", l);
}
}
return 0;
}
二分答案
利用答案与已知量之间的单调性将二分查找套用到题目中，降低时间复杂度。
例题 砍树
伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$（米），伐木机升起一个巨大的锯片到高度 $H$，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。
题解
单调性很明显，可以作为模板，直接看代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000006], n, m;
// 切 x 高度得到的木材为f(x)，f(x)单调递减
ll f(int x) {
ll ret = 0;
for(int i = 1; i <= n; i++) if(a[i] - x > 0) ret += (a[i] - x);
return ret;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
int l = 0, r = 1e9;
while(l < r - 1) {
int mid = (l + r) >> 1;
if(f(mid) >= m) l = mid;
else r = mid;
}
cout << l;
return 0;
}
习题 最小距离最大
给定$n$, $k$，输入$n$ 个数轴上的坐标值，从中选出$k$个，让这$k$个位置相邻两个之间的距离尽可能的大（即这$k-1$个距离的最小值尽量大）。输出这个最大的最小值。
题解
考虑把这些点排序后，答案（即点之间的距离）$x$的情况。显然$x$越大，我们选的点就可以更少；$x$越小，我们选的点就需要更多。设$f(x)$为答案$x$对应最少选的点数，则其单调递减。我们最终要求的$x$就是使$f(x) \ge k$的最大的$x$。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int a[MAX_N], n, k;
int f(int x) {
int ret = 1, now = a[1];
for(int i = 2; i <= n; i++) {
if(a[i] - now >= x) {
ret++;
now = a[i];
}
}
return ret;
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 0, r = (1 << 30);
while(l < r - 1) {
int mid = (l + r) >> 1;
if(f(mid) < k) r = mid;
else l = mid;
}
cout << l;
return 0;
}
双指针
也称尺取法。一种优化算法，可以优化枚举区间的效率。
例题(最短区间)
现在给定一个整数s以及一个长度为n的整数数列a[0],a[1],a[2],a[3]….a[n-1] (全为正数)，
请你求出总和不小于s的连续子序列的长度的最小值。如果解不存在，则输出0。
题解(尺取法)
不断移动区间的左右端点，实现$O(n)$的时间复杂度。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 500001;
ll sum[MAX_N];
int main() {
ll s, n, x;
cin >> s >> n;
for(int i = 1; i <= n; i++) {
cin >> x;
sum[i] = sum[i - 1] + x;
}
if(sum[n] < s) {
cout << 0;
return 0;
}
int i = 1, j = 1, minn = MAX_N;
while(j <= n) {
while(sum[j] - sum[i - 1] < s) j++;
minn = min(minn, j - i + 1);
i++;
}
cout << minn;
return 0;
}
当然这题也可以用二分(lower_bound)来做，枚举左端点，查找右端点的最小值。这样的做法时间复杂度为$O(n\log n)$。
最短的包含字符串
给出一个字符串，求该字符串的一个子串s，s包含A-Z中的全部字母，并且s是所有符合条件的子串中最短的，输出s的长度。如果给出的字符串中并不包括A-Z中的全部字母，则输出No Solution。
题解
尺取法。右指针 $i$ 向右扫描，用 $cnt_k$ 记录字母 $k$ 的出现次数，如果左端点指的字母出现次数大于$1$，就右移左指针，即可维护出最终答案。
#include <bits/stdc++.h>
using namespace std;
int cnt[27];
int main() {
string s;
int ans = 1e9;
cin >> s;
int j = 0, t = 0;
for(int i = 0; i < s.length(); i++) {
if(!cnt[s[i]- 'A']) t++;
cnt[s[i]-'A']++;
while(cnt[s[j] - 'A'] > 1) {
cnt[s[j] - 'A']--;
j++;
}
if(t == 26) ans = min(ans, i - j + 1);
}
if(t == 26) cout << ans;
else cout << "No Solution";
return 0;
}
♥