二分

题目大意 对于一个区间 $[l_i,r_i]$，计算矿石在这个区间上的检验值 $y_i$： $$ y_i=\sum_{j=l_i}^{r_i}[w_j \geqslant W] \times \sum_{j=l_i}^{r_i}[w_j \geqslant W]v_j $$ 记检验结果为 $y=\sum y_i$，对于给定的 $s$，求 $|y-s|$ 的最小值。 分析 注意到 $y(w)$ 是关于 $W$ 的递减函数，对 $w$ 在 $[w_{\min},w_{\max}]$ 上进行二分。 const ll MN = 2e5 + 10; ll vv[MN], ww[MN], li[MN], ri[MN], f1[MN], f2[MN]; ll n, m, s; int main() { n = rr(), m = rr(), s = rr(); ll minw = 0x3f3f3f3f, maxw = 0; f1[0] = f2[0] = 0; for (ll i = 1; i <= n; i++) { ww[i] = rr(), vv[i] = rr(); maxw = max(ww[i], maxw); minw = min(ww[i], minw); } for (ll i = 1; i <= m; i++) { li[i] = rr(), ri[i] = rr(); } ll l = minw, r = maxw + 1; while (l < r) { int mid = (l + r) >> 1; if (sum(mid) <= s) r = mid; else l = mid + 1; } ll rst = min(sum(l - 1) - s, s - sum(l)); printf("%lld", rst); return 0; } 区间求和可以用前缀和优化。...

题目大意 在 $0$ 到 $L$ 的位置间，有 $N$ 块岩石。若要使得岩石间距最小值最大，允许移除 $M$ 块，求此时间距最小值。 分析 定义函数 $f(x)$，输入为最小值，输出为被移除岩石的个数，实现如下 ll L, N, M, aa[100086]; ll f(ll x) { ll ans = 0; ll l = 0, r = 1; while (r <= N) { if (aa[r] - aa[l] >= x) l = r; else ans++; r++; } return ans; } 显然 $f(x)$ 是单调递减的函数，二分查找即可。 int main() { L = rr(), N = rr(), M = rr(); for (ll i = 1; i <= N; i++) aa[i] = rr(); aa[++N] = L; ll l = 1, r = L; while (l < r) { ll mid = (l + r + 1) >> 1; ll fm = f(mid); if (fm <= M) l = mid; else r = mid - 1; } printf("%lld\n", l); return 0; }