整数集合上的二分

此种写法：
1、保证最终答案处于$[l,r]$内
2、循环以$l=r$结束
3、每次二分的中间值mid会归属于左半段与右半段二者之一

while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
}
return l;
1
2
3
4
5
6
7

while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid)) l = mid;
    else r = mid - 1;
}
return l;
1
2
3
4
5
6
7

当选用 l = mid 的模版时我们需要 l + r + 1；因为否则当 r - l = 1的时候，l + r >> 1的结果为l，如果check返回true就死循环了

注意我们用的是 右移运算>>1 而不是整数除法/2，这是因为右移运算是 向下取整 ，而整数除法是 向零取整，在二分值域包含负数时后者不能正常工作

c++的那两个函数实现了在一个序列中二分查找某个整数的后继

AcWing 789. 数的范围

题意 ：

• 给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
• 对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
• 如果数组中不存在该元素，则返回 -1 -1。

#include 
using namespace std;
const int N = 1e5 + 10;

int n, q;
int a[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; ++ i) cin >> a[i];
    while (q -- ) {
        int x;
        cin >> x;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (a[l] != x) {
            cout << "-1 -1\n";
            continue;
        }
        cout << l << ' ';
        l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= x) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
}

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

AcWing 113. 特殊排序（交互）

题意 ：

• 有 N 个元素，编号 1,2…N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。不存在两个元素大小相等的情况。
• 然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 10000 次提问来获取信息，每次提问只能了解某两个元素之间的关系。现在请你把这 N 个元素排成一行，使得每个元素都小于右边与它相邻的元素。
• 例如，编号为 a 和 b 的两个元素，如果元素 a 小于元素 b，则 compare(a,b) 返回 true，否则返回 false。
• 将 N 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。
• $1\le N\le 1000$

思路 ：

• 我们借用 插入排序 的思想，假设前k-1个数已经排好序了，现在要插入第k个点，查找插入的位置
• 假设已经排好的某个数比要插入的第i个数小看作下降的线段，大看作上升的线段；那么我们只要找一个极大值，说明“这个数比要插入的数小，且它的下一个数比要插入的数大”，这就是我们需要的效果
• 我们可以采用二分，如果我们二分的这个点比它的下一个点大，那么左半边一定存在一个极大值，若小，则右半边存在一个极大值点，这样，每次范围可以缩小一半
• 我们二分出最后一个比当前要插入的这个数小的数，然后我们插入到这个数后面；如果当前mid比要插入的数小，说明它或者它右边有最后一个比要插入的数小的点，l = mid
• 边界判断，如果所有数都比要插入的数大，说明插入的数要放在第一个了

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> ans;
        ans.push_back(1);
        for (int i = 2; i <= N; ++ i) {
            int l = 0, r = ans.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (compare(ans[mid], i)) l = mid;
                else r = mid - 1;
            }
            ans.push_back(i);
            for (int j = ans.size() - 2; j >= r + 1; -- j) swap(ans[j], ans[j + 1]);    // int j + 1 = ans.size() - 1;
            if (!compare(ans[r], i)) swap(ans[r], ans[r + 1]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

实数域上的二分

以 l + eps < r 为循环条件，每次根据在mid上的判定选择r = mid 或 l = mid 分支之一即可
一般需要保留k位小数时，则取$eps=10^{-(k+2)}$

有时精度不容易确定或表示，就干脆采用循环固定次数的二分方法，这种方法得到的结果的精度通常比设置eps更高

for (int i = 0; i < 100; ++ i) {
	double mid = (l + r) / 2;
	if (calc(mid)) r = mid;
	else l = mid;
)
1
2
3
4
5

AcWing 102. 最佳牛围栏

题意 ：

• 给定正整数数列，求一个平均值最大的、长度不亚于L的连续子段
• 输出一个整数，表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。

思路 ：

• 首先本题没有出现二分的特征词：“最大值最小” or “最小值最大” 并且给的数列不具备单调性，并且不适于排序，我们看到这种题可以先提出假设 比如，假设这道题用二分能解出
• 对于二分，二分是二分性而不是单调性 只要满足可以找到一个值一半满足一半不满足即可 而不用满足单调性；
• 二分答案，判定“是否存在一个长度不小于L的子段，平均值 不小于 二分的值”
• 如果把数列中每个数都减去二分的值，就转化为判定“是否存在一个长度不小于L的子段，子段和非负”
• 若求“求一个子段，它的和最大，子段的长度不小于L”解决方案：子段和转化为前缀和相减的形式，由于随着i增长，j的取值范围$0$~$i-L$每次只会增大1，即每次只会有一个新的取值进入$min(su{m}_j)$的候选集合，所以没必要每次循环枚举j，只需要一个变量记录当前最小值，每次与新的取值取min即可
• 解决了上面这个问题后，我们只需要解决 最大子段和 是不是非负数即可了
• 注意这里要输出r，不能是l
• 当我们用实数二分求一个值的时候，这个值会趋近于答案，比如答案是6500，而l等于6499.99999，r等于6500.00001，随着精度的提高，这两边会越来越趋近于6500，这就是实数二分的特点。
• 因为它趋近于6500，所以我们知道其实答案就是6500，而答案6500向下取整就是6500，所以我们必须用r向下取整来得到答案（因为r比答案要大一点点）。
  同理，如果题目要求最终答案向上取整，就必须用l向上取整来得到最终答案（因为l比答案小一点点）

#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;

int n, m;
int a[N];
double sum[N];

bool check(double avg) {
    for (int i = 1; i <= n; ++ i) {
        sum[i] = sum[i - 1] + a[i] - avg;
    }
    double mi = 1e18;
    for (int i = m, j = 0; i <= n; ++ i, ++ j) {
        mi = min(mi, sum[j]);
        if (sum[i] - mi >= 0) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    double l = 0, r = 0;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        r = max(r, (double)a[i]);
    }
    while (l + 1e-5 < r) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(r * 1000);
}

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

三分求单峰函数极值

单峰函数拥有 唯一的极大值点，在极大值点左侧严格单调上升，右侧严格单调下降；或者拥有 唯一的极小值点，…；我们可以通过三分法求其极值

以单峰函数为例：
1、若 f(lmid) < f(rmid)：两种情况下，极大值点都在 lmid右侧，可令 l = lmid
2、若 f(lmid) > f(rmid)：极大值点在 rmid左侧，可令 r = rmid
3、若碰到 f(lmid) = f(rmid)，当函数严格单调时，令l = lmid 或 r = rmid 均可

P3382 【模板】三分法

题意 ：

• 如题，给出一个 NN 次函数，保证在范围 [l, r][l,r] 内存在一点 xx，使得 [l, x][l,x] 上单调增，[x, r][x,r] 上单调减。试求出 xx 的值。
• 第一行一次包含一个正整数 NN 和两个实数 l, rl,r，含义如题目描述所示。
• 第二行包含 N + 1N+1 个实数，从高到低依次表示该 NN 次函数各项的系数。
• 输出为一行，包含一个实数，即为 xx 的值。若你的答案与标准答案的相对或绝对误差不超过 $10^{-5}$则算正确。

#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 15;

int n;
double l, r;
double a[N];

// 秦九韶算法，已知多项式系数，由高到低遍历系数，求得多项式的值
inline double f(double x) {
    double ans = 0;
    for (int i = n; i >= 0; -- i) {
        ans = ans * x + a[i];
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> l >> r;
    for (int i = n; i >= 0; -- i) cin >> a[i];	// 系数从高到低输入
    // 单峰函数
    while (r - l > 1e-7) {
        double midl = (l + l + r) / 3;
        double midr = (l + r + r) / 3;
        if (f(midl) < f(midr)) l = midl;	// l = midl
        else r = midr;	// r = midr	
    }
    printf("%.5lf", l);
}

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

二分答案转化为判定

P1182 数列分段 Section II

题意 ：

• 给定n个数的数列，每个数对应为a[i]
• 把它们分成 连续的 m组，使T最小化，其中T表示元素之和最大的一组的和

思路 ：

• “最大值最小”，说明答案具有单调性，可用二分转化为判定
• 二分答案，判定“每组元素之和不超过二分的值”时，能否在m组 之内 把所有数分完“；注意我们二分是判定是否存在、是否可行，而不是求值

#include 
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n, m;
int a[N];

bool check(int mid) {
    int cnt = 1, now = mid;
    for (int i = 1; i <= n; ++ i) {
        if (a[i] > mid) return false;
        if (now >= a[i]) now -= a[i];
        else cnt ++ , now = mid - a[i];
    }
    return (cnt <= m);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ll sum = 0;
    int mx = 0;
    for (int i = 1; i <= n; ++ i) cin >> a[i], sum += a[i], mx = max(mx, a[i]);
    int l = mx, r = (int)min(1000000000ll, sum);
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

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

• 使用if (a[i] > mid) return false;避开

#include 
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n, m;
int a[N];

bool check(int mid) {
    int cnt = 1, now = mid;
    for (int i = 1; i <= n; ++ i) {
        if (a[i] > mid) return false;
        if (now >= a[i]) now -= a[i];
        else cnt ++ , now = mid - a[i];
    }
    return (cnt <= m);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ll sum = 0;
    for (int i = 1; i <= n; ++ i) cin >> a[i], sum += a[i];
    int l = 0, r = (int)min(1000000000ll, sum);
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

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

• 因为序列都是正整数，则序列的最小和肯定会大于等于序列中最大的数，所以将左端点定义为 l = mx

#include 
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n, m;
int a[N];

bool check(int mid) {
    int cnt = 1, now = mid;
    for (int i = 1; i <= n; ++ i) {
        if (now >= a[i]) now -= a[i];
        else cnt ++ , now = mid - a[i];
    }
    return (cnt <= m);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ll sum = 0;
    int mx = 0;
    for (int i = 1; i <= n; ++ i) cin >> a[i], sum += a[i], mx = max(mx, a[i]);
    int l = mx, r = (int)min(1000000000ll, sum);
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}
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