自动搬运

查看原文

来自洛谷，原作者为

	zhaoyp 曲终人散，悄然离场

搬运于2025-08-24 22:35:30，当前版本为作者最后更新于2022-01-17 18:57:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于 $30\%$ 的数据，暴力枚举即可，时间复杂度 $O(n^3)$。

对于 $50\%$ 的数据，加入前缀和优化即可，时间复杂度 $O(n^2)$。

对于 $70\%$ 的数据：

考虑维护中间位置 $\text{mid}$，即对于每个 $\text{mid}$，找到一个最大的 $x$，使得该 $\text{mid}$ 的前 $x$ 个元素（含 $\text{mid}$）的和与后 $x$ 个元素（不含 $\text{mid}$）的和均不大于 $m$，并用来更新该区间左端点的答案。

不难发现 $\text{mid}$ 左右段的长度具有单调性，对每一个位置进行二分答案即可，时间复杂度 $O(n \log n)$。

但是这样的维护是不完全的，因为有的答案可能是通过上法求得最长序列的部分。又注意到对于任意一个合法序列 $a$，去掉 $a$ 的第一个和最后一个元素，它依然是合法的。

于是就有如下递推式：

其中 $f_i$ 表示从第 $i$ 个元素开始的最长的优美序列的长度，$\text{DP}$ 即可，总时间复杂度 $O(n \log n)$。

对于 $100\%$ 的数据：

注意到，当 $\text{mid}$ 向右移动时，它能取到最远的左端点和右端点 $l,r$ 必定也会向右边移动。那么我们就可以用双指针（尺取法）来优化。时间复杂度 $O(n)$。

总时间复杂度 $O(n)$。