题解 P4543 【 [JSOI2011]Apple 的美食】

· · 题解

设 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}。