专栏文章

二分——学会即可碾压 90% 的程序员！

OOrange714
算法·理论参与者 58已保存评论 65

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
65 条
当前快照
2 份
快照标识符
@mjn4bsm6
此快照首次捕获于
2025/12/27 01:01
2 个月前
此快照最后确认于
2026/02/19 01:28
8 小时前
查看原文

二分算法

二分是一种比较常用的算法，是分治思想的一种体现和应用，在后续算法竞赛学习的很多题目中都有对二分的体现和运用。
此文中我们会从二分的基础逐渐过渡到二分的复杂运用和其它算法的结合。

Part 1 二分查找

通过二分查找，我们可以初步理解二分的本质和思想。

1.1 引入

猜数游戏
小 A 在 1∼1001\sim100 中在心里随机挑选一个数字，小 B 会多次猜测这个数字具体的值，如果没猜中，小 A 会告诉小 B 他猜的属比答案大还是小。
请问小 B 运用什么策略能在最坏情况下用最小的次数猜中小 A 心中想的数字？
一种最差的策略是逐个枚举，最坏情况需要猜 100100 次。
我们需要充分利用小 A 提供的猜的数和答案的大小关系，不难想到我们可以每次猜一个中间的数，根据小 A 给出的信息向左右缩小答案区间，那么每次找哪一个中间的数是最好的？
理性证明： 我们目前确定了答案在 [l,r][l, r] 中，初始 l=1,r=100l = 1, r = 100，每次会找到一个 mid∈[l,r]mid\in[l, r] 来询问小 A，如果没猜中，根据小 A 给出的答案可以把答案确定在 [l,mid−1][l, mid - 1] 和 [mid+1,r][mid + 1, r] 中。在最坏情况下，我们得到的下一个区间应该是这两个区间中长度更大的一个，那么下一个区间长度就是 L=max⁡{mid−l,r−mid}L = \max\{mid - l, r - mid\}，发现 mid=l+r2mid = \dfrac{l + r}{2} 时能使 LL 取最小值为 r−l2\dfrac{r - l}{2}，故我们每次只需要找到 ll 和 rr 的平均数，猜测并缩小答案区间，就能在最坏情况下使用最小次数猜出答案。
感性理解： 目前确定答案在一个范围内，找到中间的那个数询问，每次就一定能将这个区间缩小一半。但如果我们不选择中间的数，比如在第一次猜测时猜测 3030，如果运气好可以直接猜出或把区间缩小到 [1,29][1, 29]，但在最坏情况下会将区间缩小到 [31,100][31, 100]，这样猜数使用的次数是不稳定的。每次选中间数一定能将区间缩小一半，是最稳定的策略。
这就是二分思想，每次对目前区间的中间数进行询问，固定将区间缩小一半，猜测的次数稳定在 log⁡(区间初始长度)\log \text{(区间初始长度)}。
尝试用代码实现：
CPP
int l = 1, r = 100;
int x; // 小 A 想的数 
while (true) {
	int mid = (l + r) / 2;
	if (mid == x) { // 此次猜测为答案
		cout << mid;
		exit(0); // 结束程序
	}
	if (mid < x) l = mid + 1;
	else r = mid - 1;
}
如果你觉得上面的代码太菜了：
CPP
int x; // 小 A 想的数
cout << x;
开挂行为切勿模仿。

1.2 整数的二分查找

二分查找/靠左
给出 nn 个单调不减的非负整数 a1,⋯ ,ana_1, \cdots, a_n，进行 mm 次询问，每次询问一个非负整数 xx 在 aa 中第一次出现的位置（下标），若未出现过输出 -1。
1⩽n⩽106,1⩽m⩽105,1⩽ai,x⩽1091\leqslant n\leqslant 10^6, 1\leqslant m \leqslant 10^5, 1 \leqslant a_i, x \leqslant 10^9。
分析题目，我们确定答案的方式不能再是 mid=xmid = x 了，因为我们不能确定 midmid 是不是 xx 第一次出现在 aa 中的位置。
于是考虑逐步缩小区间，直到 l=rl = r，此时 l,rl, r 就是想要得到的答案。这也是二分最通用的写法。
对于我们找到的 midmid，该如何缩小区间？
如图，如果我们发现 amid<xa_{mid} < x，那么可以直接缩小区间到 [mid+1,r][mid + 1, r]，使得我们想要的答案（红的区间的最左边端点）依然在区间内。
如图，当 amid=xa_{mid} = x，由于我们需要查找红色区间最左侧位置，所以需要将右端点左移。那么我们要使 rr 变为 midmid 还是 mid−1mid - 1 呢？由于当前 midmid 可能是红色区域最左端，所以使 r=mid−1r = mid - 1 可能会让答案被排在区间外，所以需要使 r=midr = mid。
如图，当 amid>xa_{mid} > x，直接使 r=mid−1r = mid - 1 是没有问题的。我们在二分时习惯于分为两种情况讨论，一般会使 mid=rmid = r，与 amid=xa_{mid} = x 时一样。这样写没有问题，并且几乎不会慢多少，并且能提高代码的可读性。
最后，别忘了如果二分出来的 ll（或者 rr）不满足 al=xa_l = x，代表无解，输出 -1。
根据上述思路，可以打出以下代码：
CPP
#include <iostream>

using namespace std;

constexpr int N = 1e6 + 5;
int n, a[N], m, x;

int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	while (m --) {
		cin >> x;
		int l = 1, r = n;
		while (l < r) {
			int mid = l + r >> 1;
			if (a[mid] < x) l = mid + 1;
			else r = mid;
		}
		cout << (a[l] == x ? l : -1) << ' ';
	}
	return 0;
}
二分查找/靠右
给出 nn 个单调不减的非负整数 a1,⋯ ,ana_1, \cdots, a_n，进行 11 次询问一个非负整数 xx 在 aa 中最后出现的位置（下标），若未出现过输出 -1。
1⩽n⩽106,1⩽m⩽105,1⩽ai,x⩽1091\leqslant n\leqslant 10^6, 1\leqslant m \leqslant 10^5, 1 \leqslant a_i, x \leqslant 10^9。
按照刚才靠左查找的思路，我们可以打出以下代码（核心部分）：
CPP
int mid = l + r >> 1;
if (a[mid] <= x) l = mid;
else r = mid - 1;
欸？为什么代码 TLE 了？
运行样例，输出每次二分后的 l,rl, r，发现一直卡在了 [4,5][4, 5] 死循环，这是为什么？
答案应该为 55，但是我们每次找到的 midmid 实际上为 l+r2\dfrac{l + r}{2} 向下取整为 44，然后使 l=midl = mid，区间无变化！
解决方法很简单，由于更新 ll 时不会让 l=mid+1l = mid + 1，向右查找时应该让我们的 midmid 向上取整，避免死循环。同样的，向左查找时我们应使 midmid 向下取整，只是由于 int 类型整数除法自动向下取整的特性帮我们避免了这一错误，实际上我们考虑的是不周全的。
更正后，能写出如下正确代码：
CPP
#include <iostream>

using namespace std;

constexpr int N = 1e6 + 5;
int n, a[N], x;

int main () {
	cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	cin >> x;
	int l = 1, r = n;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (a[mid] <= x) l = mid;
		else r = mid - 1;
	}
	cout << (a[l] == x ? l : -1)
	return 0;
}
向上还是向下取整以及 ll 和 rr 取到 midmid 时要不要加减 11 就是二分中很细节和重要的部分。正是因为这些地方很容易考虑出错，所以有一句话这么说：
只有 10%10\% 的程序员能写对二分。
做题时一定要考虑好这些细节！

1.3 小数的二分查找

数的三次方根
给定一个浮点数 nn，求 nn 的三次方根，保留 66 位小数。
0⩽n⩽1040 \leqslant n \leqslant 10^4
不难发现，对于 a⩾0a\geqslant0 与 a3a^3，a3a^3 随 aa 增大而增大。那我们设 f(x)=x3f(x) = x^3，则 f(x)f(x)具有单调性。我们便可以二分查找答案 xx 使得 f(x)=nf(x) = n。
注意题目中的要求精度为 10−610^{-6}，那么我们对二分时的要求精度再小 10−210^{-2} 是最稳妥的，也就是 10−810^{-8}。那我们直接按照刚才整数域上的二分方法来二分即可，停止条件为 r−l⩽10−8r - l \leqslant 10^{-8}。
可以写出以下代码：
CPP
#include <iostream>
#include <iomanip>

using namespace std;

double n;
constexpr double eps = 1e-8;

int main () {
	cin >> n;
	double l = 1, r = 100;
	while (r - l > eps) {
		double mid = (l + r) / 2;
		if (mid * mid * mid < n) l = mid;
		else r = mid;
	}
	cout << fixed << setprecision(6) << l;
	return 0;
}
以上即为基本的二分查找，完成习题以巩固对二分思想的初步认识。

Part 2 二分答案

二分答案是二分的进阶运用，也是经常使用的算是一种 trick。我们将从简单的二分答案思想认识逐步进阶到二分答案与其它算法结合的各种题目。

2.1 基础例题

二分答案最好结合题目来理解。
木材加工
伐木场有 nn 根原木，每根的长度分别为 aia_i，现在想要锯成 kk 段长度均为 ll 的木材，请最大化 ll。
1⩽n⩽105,1⩽k,ai⩽1081\leqslant n \leqslant10^5, 1\leqslant k, a_i\leqslant 10^8。
首先可以想到暴力做法，从小到大枚举 ll，直到发现无法凑出 kk 段木材，输出。这样的时间复杂度最差是 O(n2k)\mathcal O(n^2k) 的。
理性证明： 我们可以发现，如果需要的木材长度为 ll，那么可以拼凑出的木材段数为 dl=∑i=1n⌊ail⌋d_l = \sum_{i=1}^n \lfloor\frac{a_i}{l}\rfloor，显然 did_i 单调不升。那么对于最终的答案 ll，∀ l′<l\forall ~l' < l 一定是满足要求的，而 ∀ l′>l\forall ~l' > l 是不满足要求的。所以我们可以确定答案区间后每次找到当前答案区间 [l,r][l, r] 的中间位置 midmid，判断在木材长度为 midmid 的要求下是否能得到 kk 段木材，如果满足，把下限提升到 midmid；如果不满足，把上限降低到 mid−1mid - 1。相当于一个二分靠右查找板子了。
感性理解： 如果我们要求的木材长度长，得到的数量就会少。如果我们要求的木材长度短，那么得到的数量就会多。那么一定会有一个临界点的木材长度 ll，使得我们要求在它或它以下的时候能得到至少 kk 段木材，而要求比它高时得不到。这个 ll 就是我们要求的答案。相当于合法的区间就是 [1,l][1, l]，进行一个二分靠右查找。而判断 midmid 的方式也不再是二分查找中的 amida_{mid} 和 xx 的大小关系，而变成了 O(n)\mathcal O(n) 地判断能得到多少木材，再与 kk 比较。
二分答案是什么？这个例题中我们所二分的 ll，就是这个问题的答案，也就是二分答案了。而二分中的判断变为了判断当前的答案 midmid 的可行性。我们也能发现，二分答案本质上也是二分查找，区别在于判断方式。二分查找就是一种最简单的二分答案，判断方式比较简单，可以直接比较大小而已。而我们就能从二分查找逐渐理解二分的本质。
所以我们总结出二分答案的本质，就是把找到最优答案改变为多次（log⁡n\log n 次）判断一个答案的可行性。
那是不是所有问题都能二分呢？
并不是。这道题有一个特殊的性质，就是对于木材长度对应的木材数量具有单调性，也就是二分查找中需要满足的数组的单调性。这样我们才能二分。
总结二分答案：
  • 需要使答案满足单调性才能使用。
  • 二分答案，判断可行性以缩小答案区间。
  • 设计出检查答案可行性函数在 log⁡n\log n 次询问下不超时。
那么，这道题的代码也就很好写了：
CPP
#include <iostream>

using namespace std;
using ll = long long;

constexpr int N = 1e5 + 5;
int n, k;
ll l[N], sum;

inline bool check (ll x) {
	ll cnt = 0;
	for (int i = 1; i <= n; ++ i) cnt += l[i] / x;
	return cnt >= k;
}

int main () {
	cin >> n >> k;
	for (int i = 1; i <= n; ++ i) {
		cin >> l[i];
		sum += l[i];
	}
	ll l = 0, r = sum;
	while (l < r) {
		ll mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l;
	return 0;
}
再来一道基础例题巩固一下吧！
数列分段 Section II
有一个长度为 nn 的非负整数数列 a1,⋯ ,ana_1, \cdots, a_n，现在要求把数列划分为不超过 mm 段，使得每段的和的最大值最小。求这个最小的最大值 kk。
1⩽m⩽n⩽105,0⩽ai⩽1081\leqslant m\leqslant n\leqslant 10^5, 0\leqslant a_i\leqslant 10^8。
保证答案不超过 10910^9。
还是根据二分答案的思路，我们应该先判断单调性。对于一个已经确定的 kk，我们需要分段使得每一段的和不超过当前的 kk。那么 kk 越小，分的段就会越多，也就越容易超过 mm 段的限制。那么思路就答大体已经出来了，对于答案 kk，⩾k\geqslant k 的部分分出来的块数是不多于 mm 的，所以判断可行性时，如果可行，r=midr = mid；如果不可行，l=mid+1l = mid + 1，属于一个二分靠左查找。
还有一个细节，因为一个块至少要有一个数，所以二分初始下界应该设置为 max⁡i=1nai\max_{i=1}^{n}a_i，否则需要在 check 函数里特判，比较麻烦。
CPP
#include <iostream>
#include <algorithm>

using namespace std;

constexpr int N = 1e5 + 5;
int n, a[N], m, maxa;

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

int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
		maxa = max(maxa, a[i]);
	}
	int l = maxa, r = 1e9;
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l;
	return 0;
}
完成习题以巩固对二分答案的掌握。

2.2 进阶例题

阅读此部分前请确保自己已经学习了普及组考纲内的算法和小部分提高组算法喵。
这部分会涉及二分与其它算法的结合运用。
[NOIP 2011 提高组] 聪明的质监员
小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 nn 个矿石，从 11 到 nn 逐一编号，每个矿石都有自己的重量 wiw_i 以及价值 viv_i。检验矿产的流程是：
  1. 给定 mm 个区间 [li,ri][l_i,r_i]；
  2. 选出一个参数 WW；
  3. 对于一个区间 [li,ri][l_i,r_i]，计算矿石在这个区间上的检验值 yiy_i：
yi=∑j=liri[wj≥W]×∑j=liri[wj≥W]vjy_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j
其中 jj 为矿石编号，[p][p] 是指示函数，若条件 pp 为真返回 11，否则返回 00。
这批矿产的检验结果 yy 为各个区间的检验值之和。即：∑i=1myi\sum\limits_{i=1}^m y_i。
若这批矿产的检验结果与所给标准值 ss 相差太多，就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产，所以他想通过调整参数 WW 的值，让检验结果尽可能的靠近标准值 ss，即使得 ∣s−y∣|s-y| 最小。请你帮忙求出这个最小值。
1⩽n,m⩽2×1051 \leqslant n,m\leqslant2\times10^5，0<wi,vi⩽1060 < w_i,v_i\leqslant10^6，0<s⩽10120 < s\leqslant10^{12}，1⩽li⩽ri⩽n1 \leqslant l_i \leqslant r_i \leqslant n。
思路 & 代码
对于答案 yy，显然随 WW 增加而单调不增。所以我们可以二分 WW，判断得到的 yy 与 ss 的大小关系，再进行调整，中间记录 yy 和 ss 的差维护答案。
那么如何能 O(n)\mathcal O(n) 地实现 check 函数？可以实现两个前缀和数组 pre1,pre2pre1, pre2，分别表示： pre1i=∑j=1i[wj>W], pre2i=∑j=1i[wj>W]vjpre1_i=\displaystyle\sum_{j=1}^{i}[w_j > W],~pre2_i=\displaystyle\sum_{j=1}^{i}[w_j > W]v_j 那么再对于每个询问，可以 O(1)\mathcal O(1) 地查询。得到： y=∑i=1m[(pre1r−pre1l−1)×(pre2r−pre2l−1)]y=\displaystyle\sum_{i=1}^{m}[(pre1_r - pre1_{l - 1})\times(pre2_r - pre2_{l - 1})] 总时间复杂度 O(log⁡(max⁡i=1nwj)×(n+m))\mathcal O(\log(\max_{i=1}^{n}w_j)\times(n + m))。
CPP
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
using ll = long long;

constexpr int N = 2e5 + 5;
int n, m, w[N], v[N], L[N], R[N];
ll s;
int mxw;

ll fnl = 1e18;

ll pre1[N], pre2[N];
inline bool check (int W) {
	for (int i = 1; i <= n; ++ i) {
		if (w[i] >= W) pre1[i] = pre1[i - 1] + 1, pre2[i] = pre2[i - 1] + v[i];
		else pre1[i] = pre1[i - 1], pre2[i] = pre2[i - 1];
	}
	ll y = 0;
	for (int i = 1; i <= m; ++ i) {
		y += (pre1[R[i]] - pre1[L[i] - 1]) * (pre2[R[i]] - pre2[L[i] - 1]);
	}
	fnl = min(fnl, abs(s - y));
	return y > s;
}

int main () {
	cin >> n >> m >> s;
	for (int i = 1; i <= n; ++ i) cin >> w[i] >> v[i], mxw = max(mxw, w[i]);
	for (int i = 1; i <= m; ++ i) cin >> L[i] >> R[i];
	int l = 0, r = mxw;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout << fnl;
	return 0;
}
山
给出一座山，如图。
现在要在山上的某个部位装一盏灯，使得这座山的任何一个部位都能够被看到。
给出最小的 yy 坐标，如图的 + 号处就是 yy 坐标最小的安装灯的地方。
输入第一行一个数 NN，表示这座山由 NN 个点构成；
接下来 NN 行从左到右给出了这座山的构造情况，每行两个数 Xi,YiX_i, Y_i，表示一个折点，保证 Xi>Xi−1X_i > X_{i-1}。
思路 & 代码
首先把 nn 个点转换为 n−1n - 1 条直线 y=kix+biy = k_ix + b_i
显然可以二分 yy 判断可行性。答案点 (x,y)(x, y) 应当使 ∀i∈[1,n),y⩾kix+bi\forall i\in[1, n),y \geqslant k_ix + b_i。所以对于 ki≠0k_i \not= 0 的直线，可以把对于确定的 yy 的横坐标左右范围缩小到 y−bk\frac{y - b}{k} 左右，那么可以先将 ki=0k_i = 0 的直线中最大的 bb 找出设为二分下界，再在每次判断 midmid 可行性时讨论每一条直线，将 xx 的可行区间逐步缩小，最后如果还存在可行的 xx，则具有可行性。
时间复杂度 O(log⁡(Yeps)n)\mathcal O(\log(\frac{Y}{eps})n)。
CPP
#include <iostream>
#include <iomanip>
#include <algorithm>
#define double long double

using namespace std;
using PII = pair <double, double>;

constexpr int N = 5e3 + 5;
constexpr double eps = 1e-5;
int n;
PII node[N];

struct StraightLine {
	double k, b;
} sl[N];

inline void getf (int id, PII a, PII b) {
	sl[id].k = (a.second - b.second) / (a.first - b.first);
	sl[id].b = a.second - sl[id].k * a.first;
}

inline bool check (double y) {
	double liml = 0, limr = 1e5;
	for (int i = 1; i <= n; ++ i) {
		double gtx = (y - sl[i].b) / sl[i].k;
		if (sl[i].k == 0) continue;
		if (sl[i].k > 0) {
			limr = min(limr, gtx);
		} else {
			liml = max(liml, gtx);
		}
		if (liml > limr) return false;
	}
	return true;
}

int main () {
	cin >> n;
	for (int i = 1; i <= n; ++ i) {
		cin >> node[i].first >> node[i].second;
		if (i != 1) getf(i - 1, node[i - 1], node[i]);
	}
	n --;
	double l = 0, r = 1e6, ans = 1e6;
	for (int i = 1; i <= n; ++ i) {
		if (sl[i].k == 0) l = max(l, sl[i].b);
	}
	while (r - l > eps) {
		double mid = (l + r) / 2;
		if (check(mid)) r = mid - eps, ans = mid;
		else l = mid + eps;
	}
	cout << fixed << setprecision(6) << ans;
	return 0;
}
天路
小 X 的梦中，他在西藏开了一家大型旅游公司，现在，他要为西藏的各个景点设计一组铁路线。但是，小 X 发现，来旅游的游客都很挑剔，他们乘火车在各个景点间游览，景点的趣味当然是不用说啦，关键是路上。试想，若是乘火车一圈转悠，却发现回到了游玩过的某个景点，花了一大堆钱却在路上看不到好的风景，那是有多么的恼火啊。
所以，小 X 为所有的路径定义了两个值，ViV_i 和 PiP_i，分别表示火车线路的风景趣味度和乘坐一次的价格。现在小 X 想知道，乘客从任意一个景点开始坐火车走过的一条回路上所有的 VV 之和与 PP 之和的比值的最大值。以便为顾客们推荐一条环绕旅游路线（路线不一定包含所有的景点，但是不可以存在重复的火车路线）。
于是，小 X 梦醒之后找到了你……
输入第一行两个正整数 N,MN,M，表示有 NN 个景点，MM 条火车路线，火车路线是单向的。
以下 MM 行，每行 44 个正整数，分别表示一条路线的起点，终点，VV 值和 PP 值。
注意，两个顶点间可能有多条轨道，但一次只能走其中的一条。
1⩽N⩽7×1031 \leqslant N \leqslant 7\times10^3，1⩽M≤2×1041 \leqslant M \le 2\times10^4，1⩽Vi,Pi⩽1031 \leqslant V_i,P_i \leqslant 10^3。
思路 & 代码
显然对于答案 ansans，以下都具有可行性，以上都不具有可行性，故可以二分求解。
根据题意，有：
∑Vi∑Pi⩽ans\dfrac{\sum V_i}{\sum P_i}\leqslant ans
则有：
∑Vi⩽∑Pi×ans\sum V_i\leqslant \sum P_i\times ans
则有：
∑Pi×ans−∑Vi⩾0\sum P_i\times ans - \sum V_i\geqslant 0
则有：
∑(Pi×ans−Vi)⩾0\sum(P_i\times ans - V_i)\geqslant 0
所以对于二分出的 ansans，将每条边边权设置为 Pi×ans−ViP_i\times ans - V_i，判断有没有负环即可。
温馨提示使用 bfs 版的 SPFA 判负环要超时，所以需要玄学之力 dfs 版 SPFA 判负环才能通过。
时间复杂度 O(log⁡(max⁡Vimax⁡Pi)×玄学)\mathcal O(\log(\frac{\max V_i}{\max P_i})\times 玄学)。反正能在随机数据下过。
CPP
#include <iostream>
#include <iomanip>
#include <cstring>

using namespace std;

constexpr int N = 7e3 + 5;
constexpr int M = 2e4 + 5;
int n, m;

struct Edge {
	int ver, v, p;
} e[N + M];
int head[N], nxt[N + M], tot;
inline void add (int a, int b, int v, int p) {
	e[++ tot] = Edge{b, v, p};
	nxt[tot] = head[a], head[a] = tot;
}

double dis[N];
bool vis[N];

inline bool dfs (int x, double ans) {
	vis[x] = true;
	for (int i = head[x]; i; i = nxt[i]) {
		int y = e[i].ver;
		if (dis[y] > dis[x] + ans * e[i].p - e[i].v) {
			if (vis[y]) return false;
			dis[y] = dis[x] + ans * e[i].p - e[i].v;
			if (!dfs(y, ans)) return false;
		}
	}
	vis[x] = false;
	return true;
}

inline bool check (double ans) {
	memset(dis, 0x6F, sizeof(dis));
	dis[0] = 0;
	memset(vis, false, sizeof(vis));
	return dfs(0, ans);
}

int main () {
	cin >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		int a, b, v, p;
		cin >> a >> b >> v >> p;
		add(a, b, v, p);
	}
	for (int i = 1; i <= n; ++ i) {
		add(0, i, 0, 0);
	}
	double l = 0, r = 200;
	constexpr double eps = 1e-5;
	while (r - l > eps) {
		double mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	if (l) cout << fixed << setprecision(1) << l;
	else cout << "-1";
	return 0;
}
点菜
有 nn 个人到一家餐馆点菜。这家餐馆总共有 mm 道菜，每一道菜都有两个属性——美味度和价格。这 nn 个人每周都会来一次，每次只会点一道菜或不点。在这 nn 个人中，有 pp 个人比较挑剔，他们只能接受美味度大于等于一定值的菜；有 qq 个人比较贫穷，他们只能点价格小于等于一定值的菜。现在请你计算：这些人至少要来几周，才可能能把餐馆的所有的菜都点过一遍？若来多少遍都无法点完，输出 −1-1。
p+q⩽n⩽5×104,m⩽2×105p+q \leqslant n \leqslant 5\times10^4,m \leqslant 2\times10^5。
思路 + 代码
对于答案 wekwek，显然用更多的周同样能点完所有菜，但是少任意量的时间都点不完。所以可以二分求解。
优先考虑挑剔的人，将菜品按照美味度从大到小排序，按要求的美味度从大到小处理每一个挑剔的人，由于需要考虑贫穷的人，贪心地优先吃更贵的菜，直到周数不够到或者没有能吃的菜了。然后考虑从价格要求从小到大处理贫穷的人，把所有剩下的菜从小到大排序，给当前考虑的贫穷的人吃尽可能多的他能接受的菜。最后再让没有限制的人处理剩下的菜，判断能否吃完所有的菜。
以上所有排序处理部分使用堆实现。
时间复杂度 O((n+m)log⁡m)\mathcal O((n + m)\log m)。
CPP
#include <iostream>
#include <queue>
#include <algorithm>
#define int long long

using namespace std;

constexpr int N = 5e4 + 5;
constexpr int M = 2e5 + 5;
int n, m, p, q;

struct Dish {
    int del, pri;
    friend inline bool operator < (Dish A, Dish B) {
        return A.pri < B.pri;
    }
    friend inline bool operator > (Dish A, Dish B) {
        return A.pri > B.pri;
    }
} d[M];
inline bool cmp1 (Dish A, Dish B) {
    return A.del > B.del;
}

int mindel[N], maxpri[N];

inline bool cmp (int a, int b) {
    return a > b;
}

priority_queue <Dish> tmp;
priority_queue <Dish, vector <Dish>, greater<Dish>> q2;
inline bool check (int wek) {
    if ((n - p - q) * wek >= m) return true;
    while (!tmp.empty()) tmp.pop();
    int pos = 1, done = 0;
    for (int i = 1; i <= p; ++ i) {
        for (; pos <= m and d[pos].del >= mindel[i]; ++ pos)
            tmp.push(d[pos]);
        for (int j = 1; j <= wek and !tmp.empty(); ++ j) {
            tmp.pop();
            done ++;
        }
    }
    if (done + (n - p - q) * wek >= m) return true;
    while (!q2.empty()) q2.pop();
    while (!tmp.empty()) {
        q2.push(tmp.top());
        tmp.pop();
    }
    for (; pos <= m; ++ pos) q2.push(d[pos]);
    for (int i = 1; i <= q; ++ i) {
        int cnt = 0;
        while (!q2.empty() and q2.top().pri <= maxpri[i] and cnt < wek) {
            q2.pop();
            done ++;
            cnt ++;
        }
    }
    return (done + (n - p - q) * wek >= m);
}

signed main () {
    cin >> n >> m >> p >> q;
    for (int i = 1; i <= m; ++ i) cin >> d[i].del >> d[i].pri;
    for (int i = 1; i <= p; ++ i) cin >> mindel[i];
    for (int i = 1; i <= q; ++ i) cin >> maxpri[i];
    sort(d + 1, d + m + 1, cmp1);
    sort(mindel + 1, mindel + p + 1, cmp);
    sort(maxpri + 1, maxpri + q + 1);
    int l = 1, r = m, ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}
完成习题以巩固知识。
完结撒花！

评论

共 65 条评论，欢迎与作者交流。

正在加载评论...