wqs二分学习笔记

技术分享 2年前 (2022-07-13) 0 999+

关注

引入

是什么？能用来解决什么问题？

序列 (a) 有 (n) 个元素，求选正好 (k) 个元素和的最大值？

这道题可以用排序，但是这道题可以用来理解 wqs 二分的思路。
用 (g_k) 表示选恰好 (k) 个元素的最佳答案，把 ((k,g_k)) 形成的点画在坐标系上，就能得到一个「上凸包」。

例如 (a = [9,8,4,2,-9,-15]) 时，

对于大多数题目，如果没有 (k) 的限制（即取的次数的限制），应该是可以在可观的复杂度内如 (mathcal{O}(n)) 得出答案，比如这道题就是把所有正数加起来，答案相当于求凸包的最高点纵坐标。
但是有了准确的次数限制之后就行不通了。

wqs 二分的作用就是能利用这个和 (k) 与答案关系的斜率的单调性，二分一条直线的斜率来切凸包。

什么是切凸包？

wqs 二分的 check 环节在切凸包。

有了一个确定斜率 (c) 的直线之后，假设与凸包切在一个点 ((p,g_p))，那么此时一定满足直线的「截距」最大，为 (g_p-ccdot p)。

这个可以看作是在每个元素基础上加上一个代价 (c)，就是对于每个元素减 (c) 后，计算不带元素个数限制的本问题的答案 (texttt{Maxn})，结果就能得到 ((p,g_p)) 这个点，即 (texttt{Maxn} + ccdot p = g_p)。

形象地理解，加上代价之后凸包变形，求变形凸包的最高点等同于原来用 (c) 斜率的直线切凸包，切出来就是最大的截距。

如下图所示，(A'B'C'D'E'F'G') 便是上图变形后的凸包，点 ((i,p_i)) 由于加上代价，移动到 ((i,p_i-ccdot i))。可以看出，切凸包的斜率为 (c) 的线，切到的点就是单次加上代价 (c) 后的答案 (texttt{Maxn})。

动态演示 By qzhwlzy

高级的动态演示

动态演示

不断改变 (c)，因为斜率具有单调性，可以看出 (p) 是随着 (c) 单调变化的。所以通过不断二分 (c)，可以找到需要的 (k) 的限制。

当然这只是一个思想，还有许多细节需要注意。

例题

买卖股票的最佳时机 IV

套用上面的套路可以发现，答案与限制条件之间的关系是满足 (k) 与答案关系的斜率有单调性，加上代价后的答案可以使用线性的 DP 或贪心计算。

点击查看不带限制的 DP 写法

int f[100010][2]; int g[100010][2];  int num, ans; void fee(int k) { // k 表示每笔交易附加的费用，用于二分 	f[0][1] = -1e9, f[0][0] = 0; 	for (int i = 1; i <= n; i++) { 		if (f[i - 1][0] < f[i - 1][1] + a[i]) 			f[i][0] = f[i - 1][1] + a[i], g[i][0] = g[i - 1][1]; 		else 			f[i][0] = f[i - 1][0], g[i][0] = g[i - 1][0]; 		if (f[i - 1][1] < f[i - 1][0] - a[i] - k) //这样求出来的交易次数也是最小的 			f[i][1] = f[i - 1][0] - a[i] - k, g[i][1] = g[i - 1][0] + 1; 		else 			f[i][1] = f[i - 1][1], g[i][1] = g[i - 1][1]; 	} 	ans = f[n][0]; 	num = g[n][0]; }

由于我们知道答案都是整数，斜率只需要二分整数就行了，一定能二分到 (k) 的一段。

点击查看二分代码

int main() { 	int i, k; 	int l = 0, r = 1, mid, Ans = -1; 	cin >> n >> k; 	for (i = 1; i <= n; i++) 		cin >> a[i], r = max(r, (int)a[i]); 	while (l <= r) { 		mid = (l + r) / 2; 		fee(mid); 		if (num <= k) { 			Ans = k * mid + ans; 			r = mid - 1; 		} else { 			l = mid + 1; 		} 	} 	if (Ans == -1) { 		fee(0); 		cout << ans << endl; 	} else 		cout << Ans << endl; 	return 0; }

细节解析：

if (Ans == -1) 在此情况下二分失败，说明 (k) 在非正斜率的部分，直接忽略 (k) 的限制进行贪心可行；
Ans = k * mid + ans; 我们当前切到的点在 ((texttt{num},texttt{num} cdot texttt{mid} + texttt{ans}))，为什么不写 Ans = num * mid + ans; 呢？

这就要说一个很恶心的情况了。如果凸包上三点共线，我们只能取到上面的一些特殊点（如最左最右的点），不一定取到 (k)；如果读者想要尝试，本题目中以下样例存在该情况：

Hack 数据