wqs二分学习笔记

序列 \(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-c\cdot p\)。

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

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

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

高级的动态演示

动态演示

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

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

套用上面的套路可以发现，答案与限制条件之间的关系是满足 \(k\) 与答案关系 的斜率有单调性，加上代价后的答案可以使用线性的 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;
}

细节解析：

1. if (Ans == -1) 在此情况下二分失败，说明 \(k\) 在非正斜率的部分，直接忽略 \(k\) 的限制进行贪心可行；

2. Ans = k * mid + ans; 我们当前切到的点在 \((\texttt{num},\texttt{num} \cdot \texttt{mid} + \texttt{ans})\)，为什么不写 Ans = num * mid + ans; 呢？

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

8 2
3 3 5 0 0 3 1 4

于是，我们用 DP 处理交易次数最大值，在 \(\texttt{num} \ge \texttt{k}\) 时更新答案，只需要最后一次，但因为不一定能取到等号，所以最好都更新。

或者，我们用 DP 处理交易次数最小值，在 \(\texttt{num} \le \texttt{k}\) 时更新答案，只需要最后一次（而且不能使用 \(\max\)），但因为不一定能取到等号，所以最好都更新。

此外在上面的例子中，我们还发现，k * mid + ans 似乎也有一些单调性，(mid,k * mid + ans) 构成的点很像下凸包......不过我们暂时不研究 其实是不会到时候填坑吧

这道题完美符合上述特点，同样需要注意三点共线情况。写法同样有两种。
写法1
写法2

与上相同。三份代码详情