二分答案
在线性表章节已了解二分查找的基本原理，当一个问题的答案具有单调性时——即随着答案的增大或减小，判定条件的结果也呈现单调变化，比如答案越大条件越容易满足，或者答案越小条件越容易满足，可以通过二分查找，在过程中根据判定条件是否满足来调整二分的方向逼近解的过程。
例：一元三次方程求解
给定一个一元三次方程 \(ax^3 + bx^2 + cx + d
= 0\)，其中系数 \(a, b, c, d\)
均为实数，并已知该方程有三个不同的实根，这些根的范围在 \(-100\) 至 \(100\) 之间，且任意两根间的差的绝对值 \(\geq
1\)。请按从小到大的顺序在同一行输出这三个实根（精确到小数点后两位，并留有空格）。
输入：4个实数
输出：3个保留2位小数的实根
题目给的关键条件是数据确保根的距离大于 \(1\)，也即相邻两个整数的左闭右开区间中至多 1
个解。如果某个这样的区间有解，则必然两端的 \(f(x)\) 不可能在 \(x\) 轴的同一侧，即 \(f(x_{1})*f(x_{2}) \leq 0\)。
思路：枚举每个长度为 1 的区间，判断两端是否不在 \(x\)
轴同侧，如果不在同侧，说明区间内有解，二分 \(x\) 的值，直到它的函数值为 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<cstdio>
const double eps = 1e-7;
double f(double x, double a, double b, double c, double d) {
return a * x * x * x + b * x * x + c * x + d;
}
int main() {
double a, b, c, d;
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
for(int i = -100; i <= 100; i ++) {
double l = i, r = i + 1;
double fl = f(l, a, b, c, d), fr = f(r, a, b, c, d);
if(-eps < fl && fl < eps) {
printf("%.2f ", l);
} else if(-eps < fr && fr < eps) {
continue;
} else if(fl * fr < eps) {
for(int j = 0; j < 100; j ++) {
double mid = (l + r) * 0.5;
double fm = f(mid, a, b, c, d);
if(fm * fl < eps) r = mid;
else l = mid;
}
printf("%.2f ", l);
}
}
printf("\n");
return 0;
}
|
知识点： 浮点精度冗余 eps。
浮点类型在计算机底层也是由有限位的二进制01表达的，就必然有精度限制，不能无限精确地表达任何数字，如果发生乘除法，这种精度会进一步丢失，当判断两个浮点数是否相等、一个浮点数大于0还是小于0的时候，用一个极小的浮点数作为精度冗余，比如对浮点数
fl， if(fl == 0)
就是不安全的，它在丧失一定精度后，可能是
0.0000312141，也可能是-0.0000012131，
eps
是我们对特定问题期望的一个“可接受”精度，const double eps=1e-7
就表示在 10^{-7}（0.0000001）
范围内的误差都认为相等，1e-7
是算法题比较常用的一个精度，视具体问题，也有时会用
1e-6或1e-8。
知识点： 浮点数二分的时候，while(r - l > eps)
是循环条件的常见写法，但一些刁钻的题可能精度不好把握，for(int j = 0; j < 100; j ++)
直接二分100次，基本什么精度都能达到了，在分析好算法复杂度满足题意的情况下，这样写更加稳定。
例：数列划分
给一个有 \(n\)
个正整数的序列，连续地将其分为互不重叠的 \(k\)
份，即每一份都是该序列的一个子串，不能调换顺序。
求一个划分方案，使数字之和最大的那一份，其和在所有划分方案里最小。
输入
1
2
| 9 3
10 20 30 40 50 60 70 80 90
|
输出
1
| 10 20 30 40 50 / 60 70 / 80 90
|
二分答案常常伴随着贪心策略——二分可能的答案数值，在验证判定条件时，往往会需要一个复杂度较低的策略，当判定条件支持贪心时，就有更大的可能让二分答案的复杂度低于其它方案。
当指定一个“数字之和最大的那一份”的限制时，实际就是尝试构造一个划分，让每一份都不超过这个限制，如果无法实现，则判定为“否”，如果能实现，则判定为“是”，限制值与判定关系是单调的——值够大就一定能成功划分，值小到一定程度就一定无法划分，那么能否完成划分的临界点，就是本题答案——最大那一份最小的划分。
划分的判定采用贪心策略，因为划分并不改变顺序，那就让每一份尽可能的靠近限制值，直到装不下，再开始划分下一份。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <complex>
#include <vector>
const int maxn = 1e5 + 10;
int n, k, a[maxn];
bool split[maxn];
bool Judge(int mid) {
int cnt = 1, tmpsum = 0;
for (int i = 0; i < n; i++) {
if (a[i] > mid) return false;
if (tmpsum + a[i] > mid) tmpsum = 0, cnt++;
tmpsum += a[i];
if (cnt > k) return false;
}
return true;
}
int main() {
while (scanf("%d%d", &n, &k) != EOF) {
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int left = 0, right = 1e9, mid;
while (left < right) {
mid = left + right >> 1;
if (Judge(mid))
right = mid;
else
left = mid + 1;
}
int tmpsum = 0, cnt = 0;
memset(split, 0, sizeof(split));
for (int i = n - 1; i >= 0; i--) {
if (tmpsum + a[i] > left || i + 1 < k - cnt)
tmpsum = 0, split[i] = true, cnt++;
tmpsum += a[i];
}
for (int i = 0; i < n; i++) {
printf(" %d" + !i, a[i]);
if (split[i]) printf(" /");
}
printf("\n");
}
return 0;
}
|