168E

题面 给定长度为 \(n\) 的数列 \(\{a_i\}\) 和两个参数 \(k, s\)，将 \(\{a_i\}\) 划分成 \(k\) 段，最大化 和 \(\geq s\) 的段数。 \(1 \leq k \leq n \leq 250000, 1 \leq A_i \leq 10^9, 1 \ ......

题目链接 看到严格选 \(k\) 个，不难想到 WQS二分。定义 \(f(x)\) 为分成 \(x\) 段，最多有多少个超过 \(S\) 的。然后你会发现他不是凸的。因为他有很多平段，比如把两个很小的合并不改变答案。 换个方向？ 考虑定义 \(f(x)\) 为有 \(x\) 个超过 \(S\) 的段 ......

有点意思的简单题。 答案有可二分性。合并两段，显然仍然合法。 考虑如何 check。因为答案可以被二分，我们尝试求恰好 \(x\) 段就行了。 恰好，这是 wqs 二分的内容。如何设计一个与 \(x\) 有关的凸函数呢？ 这个函数大概是 \(\sum_{i=1}^x w(l_i, r_i)\) 的形 ......

简要题意 给定一个长度为 $n$ 的序列 $a$，将 $a$ 划分为 $k$ 个连续段，最大化满足连续段中元素和 $\geq s$ 的连续段数。 题解 首先发现是恰好 $k$ 个连续段，这种类型的题套路地考虑 wqs 二分，然后你会惊喜的发现这玩意不是凸的，我的思考也就卡在这里了。 正确的做法是观察 ......