---

整数集上的二分

---

范围规定在[l, r]之内，循环结束条件为l = r，中间值mid归属于左半或右半。

递增序列查找 ≥x 的数中最小的一个（x 或 x 的后继）：

while(l < r){
	//x << y 可理解为 x * 2^y
	//x >> y 可理解为 x / 2^y
	//实数不能用以上操作，要用"/"号
	int mid = (l + r) >> 1;
	if(arr[mid] >= x){
		r = mid;
	} else {
		l = mid + 1;
	}
}
return arr[l];

递增序列查找 ≤x 的数中最大的一个（x 或 x 的前驱）：

while(l < r){
	int mid = (l + r) >> 1;
	if(arr[mid] <= x){
		l = mid;
	} else {
		r = mid - 1;
	}
}
return arr[l];

实数域上的二分

---

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

while(l + 1e-5 < r){
	double mid = (l + r) / 2;
	if(calc(mid))
		r = mid;
	else
		l = mid;
}

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

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

1. Best Cow Fences AcWing102

---

输入样例：

10 6
6
4
2
10
3
8
5
9
4
1

输出样例：

6500

#include <iostream>

using namespace std;

const int N = 100010;
int arr[N];
double sum[N];
int n, f;

bool check(double avg){
	//计算前缀和
	for(int i = 1; i <= n; i++){
		sum[i] = sum[i - 1] + (arr[i] - avg);
	}
	
	double minN = 0;
	for(int i = 0, j = f; j <= n; i++, j++){
		minN = min(minN, sum[i]);
		//前缀和相减变为部分和（题目中要求的连续序列和）
		//这里使用minN而不是sum[i]就可以达成题目中的j-i>=f的条件
		if(sum[j] - minN >= 0)
			return true;
	} 
	return false;
}

int main(){
	cin >> n >> f;
	double l = 0, r = 0;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
		r = max(r, (double)arr[i]);
	}
	
	//模板
	while(l + 1e-5 < r){
		double mid = (l + r) / 2;
		if(check(mid))
			l = mid;
		else
			r = mid;
	}
	
	cout << (int)(r * 1000);
	
	return 0;
}

2. Innovative Business AcWing113

---

输入样例：

每个元素的有向图，数字1代表比那个位置上的元素小。

[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例：

输出的是元素编号。

[3, 1, 2]

思路： 数学归纳法，假设前k – 1个数都已排好序，则确定第k个数在其中位置即可。首先找到前k – 1的mid处，与k进行比较，若k比其小，则令r = 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> vec;
        vec.push_back(1);
        
        for(int i = 2; i <= N; i++){
            int l = 0, r = i - 1; // 边界选取[1, i], 从1开始计, 因为vector是从0开始的, 所以左右边界-1, 此时, 右边界也可以写成vec.size()。
            int mid;
            
            while(l != r) {
                mid = (l + r) / 2;
                if(compare(i, vec[mid])) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            
            vec.insert(vec.begin() + l, i); // 切记不能写成 + mid, 因为在else的情况中, l = mid + 1。
        }
        
        return vec;
    }
};

视频讲解

https://pan.baidu.com/s/1bZ8unSLzfO2CfLH3nO8fEg?pwd=225f 提取码: 225f