学习笔记（一）二分法

整数二分规范

介于二分取左右边界的不确定性和容易陷入死循环的问题，笔者这里自己总结一点学习小技巧

先写出未完善二分模板

int fun(int n){
	int l=0,r=n;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;//或者r=mid
		else r=mid-1;//或者l=mid+1
	}
	return l;
}

2.通过题干条件完善check以及后面的mid的转移

check内部根据题干完成，后边根据要求看l=mid还是r=mid，这些完成后else后面的语句自然就完成了。

3.看if或者else后边的语句，根据其压缩到哪个边界选择mid是左中位数还是右中位数

首先，这里讲解左右中位数，取小运算左中位数，反之取大运算是右中位数。对于 (l+r)/2 这个语句在 l+r 为正数的时候才是取左中位数，为负数时是右中位数，所以一般不用整除，采用 (l+r)>>1 作为左中位数，避免这种问题，而右中位数则是 (l+r+1)>>1 。

然后，看if后边的语句才是记录着答案（符合check的答案），意味着else后边的语句会在结束的时候向if后边的语句收敛（或者if后带着答案收敛于else）。因为else后语句不可避免要+1或者-1因为整数二分要避免死循环，但是就算如此中位数压缩到左右不对也会导致死循环。

最后，这里我们拿else后语句为 r=mid-1 举例，反之亦然。r会收敛于l，如果mid使用左中位数，答案会向左边界压缩，而语句中 l 记录着答案，l直接等于mid没有+1的改变，所以压缩到 l 时会导致死循环。所以这里我们使用右中位数，避免左中位数压缩左边导致的死循环。

总结，哪个会动采用哪边的中位数，哪个会动看else后语句，即else语句后是r则用右，是l则用左。

如此我们便完成了整数二分的规范，避免了死循环且答案压缩在if后面的语句（实际上最后l=r，哪个都可以），这里用单调递增数列二分检索x和x的前驱（即找到第一个小于等于x的数）举例

int fun(int a[],int n,int x){
	int l=0,r=n-1;//这里初值的选取可以用特殊值，看最后收敛至哪里需求改变（其实也可以设置特别宽）
	while(l<r){
		int mid=(l+r+1)>>1;//因为第六行，所以用右中位数
		if(a[mid]<=x) l=mid;//答案保存在l中
		else r=mid-1;//r会改变
	}
	return l;
}

总结：1.写出未完善代码 2.完善check及后面语句 3.根据else后语句选择中位数

可以参考如下习题，（一）中第一道压缩至右边界（选择左中位数），第二道压缩至左边界。

二分习题练习

（一）最大值最小化（最小值最大化）

题目建模：

一般这种题目采用二分思路

洛谷P1462

附链接https://www.luogu.com.cn/problem/P1462

题面

建模：

x为边权，x<=b

st. y=max{fi} fi所连成总边权x<=b

求 min{y}

思路：对点权二分，检查到当前点权fi时删除所有大于fi的点，对剩余点用dijkstra算法（优先队列优化后），检查是否满足x<=b，算法时间复杂度O(mlognlogn)

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 1e4 + 5;
const int INF = 0x3fffffff;
const double eps = 1e-7;
typedef long long ll;
const int modp = 1e6 + 37;

typedef struct ff {
	ll pos;
	ll data;
	bool operator <(const ff &a) {
		return data < a.data;
	}
} F;

typedef struct mm {
	ll p;
	ll d;
	bool operator >(const mm &a)const {
		return d > a.d;
	}
} M;

F f[N];
ll n, m, b;
vector<ll> son[N], w[N];
bool vis[N];
ll dist[N];

ll dj() {
	if (!vis[1])
		return INF;
	priority_queue<M, vector<M>, greater<M> > pq;
	ll visnum = 0;
	rep(i, 1, n) dist[i] = INF;
	rep(i, 1, n) if (vis[i])
		visnum++;
	rep(i, 1, son[1][0]) if (vis[son[1][i]]) {
		M tmp;
		tmp.p = son[1][i];
		tmp.d = w[1][i];
		pq.push(tmp);
		dist[son[1][i]] = w[1][i];
	}
	rep(i, 1, visnum - 1) {
		if (pq.empty())
			break;
		ll pos = 0, dis = INF;
		while (!vis[pos]) {
			M tmp = pq.top();
			pq.pop();
			pos = tmp.p;
			dis = tmp.d;
			if (dist[pos] != dis)
				continue;
		}
		if (pos == 0)
			continue;
		rep(j, 1, son[pos][0]) {
			if (vis[son[pos][j]] && dist[son[pos][j]] > w[pos][j] + dis) {
				dist[son[pos][j]] = w[pos][j] + dis;
				M tmp;
				tmp.d = dist[son[pos][j]];
				tmp.p = son[pos][j];
				pq.push(tmp);
			}
		}
	}
	return dist[n];
}

bool check(int x) {
	vis[0] = false;
	rep(i, 1, n) if (i <= x)
		vis[f[i].pos] = true;
	else
		vis[f[i].pos] = false;
	ll dis = dj();
	if (dis <= b)
		return true;
	return false;
}

void solve() {
	sort(f + 1, f + n + 1);
	ll l = 1, r = n + 1;
	while (l < r) {
		ll mid = (l + r) >> 1;
		if (check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	if (l == n + 1)
		cout << "AFK";
	else
		cout << f[l].data;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> b;
	rep(i, 1, n) {
		ll x;
		cin >> x;
		f[i].pos = i;
		f[i].data = x;
	}
	rep(i, 1, n) son[i].push_back(0), w[i].push_back(0);
	rep(i, 1, m) {
		ll a, b, c;
		cin >> a >> b >> c;
		if (a == b)
			continue;
		son[a].push_back(b);
		son[a][0]++;
		son[b].push_back(a);
		son[b][0]++;
		w[a].push_back(c);
		w[b].push_back(c);
	}
	solve();
	return 0;
}

洛谷P1824

附链接https://www.luogu.com.cn/problem/P1824

题面

建模：

条件：c头牛在xn个坐标上

y=dist(xi,xj)

求 max{y}

思路：二分距离y，检查y是否满足c头牛都在坐标上。

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 1e5 + 5;
const int INF = 0x3fffffff;
const double eps = 1e-7;
typedef long long ll;
const int modp = 1e6 + 37;

int n, c;
int a[N];

bool check(int x) {
	int i = 1, j = 1;
	int sum = 1;
	while (j <= n) {
		while (j <= n && a[j] - a[i] < x)
			j++;
		if (j > n)
			break;
		sum++;
		i = j;
	}
	if (sum >= c)
		return true;
	return false;
}

void solve() {
	int l = 0, r = a[n] - a[1];
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (check(mid))
			l = mid;
		else
			r = mid - 1;
	}
	cout << l;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> c;
	rep(i, 1, n) cin >> a[i];
	sort(a + 1, a + n + 1);
	solve();
	return 0;
}

这里选择一道实数二分，相比整数二分考虑的就没有那么多了，注意精度问题，精度过大错误，精度过小超时

POJ 2018 最大平均字段和

附链接http://poj.org/problem?id=2018

题面

建模：

条件：j-i>=F

st. y=(a[j]-a[i])/(j-i)

求 max{y}

思路：这是一道最大平均字段和问题，二分平均值，检查y时找到一个平均字段和大于等于y，判断这个字段的长度是否小于F。这里对数组中每个元素a[i]都减去y即 a[i]=a[i]-y 然后求其前缀和，我们找所有长度大于等于F的前缀和，判断其是否大于等于0就好。当前前缀和-F个位置之前的最小前缀和就是当前位置长度大于等于F的最大区间和。

#include<iostream> //poj不能用万能头
#include<cstdio>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 1e5 + 5;
const int INF = 0x3fffffff;
const double eps = 1e-5;
typedef long long ll;
const int modp = 1e6 + 37;

int n, f;
double a[N];

bool check(double x) {
	double b[N];
	b[0] = 0;
	rep(i, 1, n) {
		b[i] = a[i] - x;
		b[i] += b[i - 1];
	}
	double minn = INF;
	double maxsum = -INF;
	rep(i, f, n) {
		minn = min(b[i - f], minn);
		maxsum = max(maxsum, b[i] - minn);
	}
	return maxsum >= 0;
}

void solve() {
	double l = 0, r = 2005;
	while ((r - l) > eps) {
		double mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	cout << (int)(r * 1000);//这里答案压缩在右边界
}

int main() {
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	while (scanf("%d%d", &n, &f) == 2) { //poj这里不这样处理会死循环而超时
		rep(i, 1, n)scanf("%lf", &a[i]);
		solve();
	}
	return 0;
}

poj有一些问题需要注意，double和负值情况也需要注意。

这里留下个疑问，答案压缩在左边界就wa了，实数二分理应左右边界均可以，观察很多实数二分代码均打印else后答案。

欢迎lao来解答。