自动搬运

查看原文

来自洛谷，原作者为

	xgzc 苔花如米小，也学牡丹开。

搬运于2025-08-24 22:01:09，当前版本为作者最后更新于2020-02-16 17:09:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

设 $A(l, r) = \sum_{i=l}^r a_i, B(l, r) = \sum_{i=l}^r b_i$。

所求就是 $\frac{2A(l, r)}{A(1, n) + B(l, r)}$。

60 pts

分数规划，二分答案后有：$2A(l, r) - \mathrm{mid} (A(l, r) + B(l, r)) \geq \mathrm{mid} * A(1, n)$。

令 $c_i = 2a_i - \mathrm{mid}(a_i + b_i)$，跑一个最大子段和即可。

时间复杂度 $\mathcal O(Tn\log n)$。

100 pts

发现这两个序列 $a, b$ 有周期且周期不超过 $m$。

所以答案要么不包含一个完整的周期，要么包含。

暴力枚举周期内的点，利用周期的性质计算答案。

时间复杂度 $\mathcal O(Tm^2)$。

代码见我的 $\texttt{blog}$。