分割使方差和最大
P5520. 分割使方差和最大
场次:2026年10月20日-非AI方向 · 来源:CodeFun2000 P5520
题目描述
给定一个长度为 的整数数列 ,你需要找到一个分割点 (),将数列划分为前后两部分 和 ,使得 的方差与 的方差之和最大。
方差定义为
输入格式
第一行输入一个整数 (),表示数列长度。
第二行输入 个整数 (),表示数列元素,以空格分隔。
输出格式
输出一个浮点数,表示方差之和的最大值,保留 位小数。
示例
示例 1
输入:
3
-1 9 -9输出:
81.000000说明: 在 处切开:左段 的方差为 ,右段 的均值为 、方差为 ,和为 。
示例 2
输入:
4
2 1 7 2输出:
6.888889说明: 与 都能取到最大值 。 时左段 方差为 ,右段 方差为 。
解题思路
判定标准:两个「总体方差」相加,除以段长而不是段长减一
先把这个「方差」钉死:题面用的是总体方差,除以段内元素个数 ,不是样本方差的 。这一个分母决定了单元素段的方差是 ——单点没有任何离散度,这一点在切分位置贴着两端时会频繁出现。
于是问题的判定标准很直白:枚举每个合法的 ,算出
取最大值,按 位小数输出。没有次级目标,也没有字典序要求,只要这个和最大。
方差只需要三个数:长度、元素和、平方和
把方差的定义展开,会得到一个只用「和」与「平方和」就能算的形式。设段内有 个元素,和为 ,平方和为 ,平均值 :
第二步到第三步用了 (所以 ),最后一步把 代回去。结果是
也就是「平方的平均」减去「平均的平方」。写成一个函数:
def var(lo, hi):
"""下标区间 [lo, hi) 的总体方差。"""
length = hi - lo
s = pre[hi] - pre[lo] # 段内元素和
s2 = pre2[hi] - pre2[lo] # 段内平方和
mean = s / length
return max(0.0, s2 / length - mean * mean) # 浮点抵消可能给出 -0.0末尾的 max(0.0, ...) 是给浮点抵消留的余地:数学上方差不可能为负,但两个相近的大数相减会掉出 这样的尾巴,扣在答案上就会变成 -0.000000。
前缀和把每个切割点压到 O(1)
上面的函数要「段内元素和」与「段内平方和」。如果每个切割点都从头累加一遍,光求和就是 , 个切割点合起来是 ——同一批前缀被反复相加,全是重复劳动。
把这两样都做成前缀数组即可:
pre = [0] * (n + 1) # 前缀和
pre2 = [0] * (n + 1) # 前缀平方和
for i, v in enumerate(a, 1):
pre[i] = pre[i - 1] + v
pre2[i] = pre2[i - 1] + v * v之后任意一段 的和是 pre[hi] - pre[lo],平方和是 pre2[hi] - pre2[lo],两次减法都是 。切割点 把数组分成 与 ,一次循环就能把所有位置试完:
best = -1.0
for k in range(1, n): # 左段 [0, k),右段 [k, n)
cur = var(0, k) + var(k, n)
if cur > best:
best = curbest 初值取 :方差和非负,任何合法切法都会把它顶上去,省掉「是不是第一个」的判断。
为什么要用前缀和而不是直接存浮点方差:前缀和全是整数的累加。按题面范围,元素最大 ,平方和能到 量级,Python 的整数运算不掉一位精度;只在最后除以长度时才转成浮点。如果一开始就用浮点累加前缀,误差会随项数线性增长,大数相减时尤其明显。
输出:f"{best:.6f}" 才是「6 位小数」
题目要的是固定 6 位,包括末尾的 0。round(best, 6) 只做四舍五入、不做补零,示例 1 的 会原样打印成 81.0;f"{best:.6f}" 才会给出 81.000000。
print(f"{best:.6f}")实现落点
pre/pre2是长度 的数组,pre[0] = pre2[0] = 0,方便区间做差;var(lo, hi)用半开区间,左段传(0, k)、右段传(k, n),边界不用单独处理;- 分割点循环是
range(1, n):k = 0与k = n都会让某一段长度为 ,既不是合法切法,也会让var里出现除以 ; - 只有一处的浮点运算发生在
var内部,比较与输出都用同一个best,不会再引入第二份误差。
完整代码实现
"""
P5520. 分割使方差和最大 - 前缀和 + 前缀平方和
把一个数列在下标 k(1 <= k < n)处切成左右两段,求两段方差之和的最大值,
保留 6 位小数输出。方差取总体方差:
Var(X) = (1/|X|) * Σ(x_i - mean)^2 = E[x^2] - (E[x])^2。
输入格式:
- 第 1 行:整数 n(n >= 2);
- 第 2 行:n 个整数(空格分隔)。
输出格式:
- 一个实数,保留 6 位小数。
核心思路:
方差只需要「长度、元素和、平方和」三样东西:
Var = S2 / len - (S / len)^2
两段分别用前缀和与前缀平方和做差即可 O(1) 求出。枚举 n-1 个分割点,
取方差和的最大值。前缀和都用整数存,只在算方差时转成浮点,
既能保住大整数相加的精度,也不用为每个分割点重扫一遍数组。
"""
# https://codefun2000.com/p/P5520
import sys
# @sample-start
"""
样例输入 1:
3
-1 9 -9
样例输出 1:
81.000000
"""
# @sample-end
# @sample-start
"""
样例输入 2:
4
2 1 7 2
样例输出 2:
6.888889
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
a = list(map(int, data[1 : 1 + n]))
pre = [0] * (n + 1) # 前缀和
pre2 = [0] * (n + 1) # 前缀平方和
for i, v in enumerate(a, 1):
pre[i] = pre[i - 1] + v
pre2[i] = pre2[i - 1] + v * v
def var(lo, hi):
"""下标区间 [lo, hi) 的总体方差。"""
length = hi - lo
s = pre[hi] - pre[lo]
s2 = pre2[hi] - pre2[lo]
mean = s / length
return max(0.0, s2 / length - mean * mean) # 浮点抵消可能给出 -0.0
best = -1.0
for k in range(1, n): # 左段 [0, k),右段 [k, n)
cur = var(0, k) + var(k, n)
if cur > best:
best = cur
print(f"{best:.6f}")
def run_tests():
"""运行嵌入的示例与边界用例,方便本地自测。"""
import io
cases = [
# 示例 1:k=1 时右段 [9,-9] 方差 81,和为 81
("3\n-1 9 -9\n", "81.000000"),
# 示例 2:k=1 或 k=3 时取到 62/9 ≈ 6.888889
("4\n2 1 7 2\n", "6.888889"),
# 两个元素:两段都是单点,方差和恒为 0
("2\n7 9\n", "0.000000"),
# 全相等:任何切法都是 0
("5\n5 5 5 5 5\n", "0.000000"),
# 左段 [-4,4] 均值 0、方差 16,右段 [4] 方差 0
("3\n-4 4 4\n", "16.000000"),
# 大数:平方和到 1e18 量级,检验整数前缀和的精度
("3\n1000000000 1000000000 1000000000\n", "0.000000"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected}, 实际={output} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:
前缀和 ,前缀平方和 。,两个切点逐个算:
| 左段 | 左段方差 | 右段 | 右段方差 | 和 | |
|---|---|---|---|---|---|
| , | , | ||||
| , | , |
最大值是 ,在 处取到,按 位小数输出 81.000000。 只有 :把 与 塞进同一段后,两段的离散度都变小了。
示例 2:
前缀和 ,前缀平方和 。
| 左段 | 左段方差 | 右段 | 右段方差 | 和 | |
|---|---|---|---|---|---|
| , | |||||
| , | , | ||||
| , |
, 与 并列最大,按 位小数输出 6.888889。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每个切割点重扫两段求和与平方和 | 同一批前缀被反复累加, 大时超时 | ||
| 前缀和 + 前缀平方和(最优) | 两次前缀各扫一遍,之后每个切割点 |
前缀数组各占 个整数,其余只有常数级变量。
易错点总结
1. 方差第二项少除了一次长度
把 s2 / length - mean * mean 写成 s2 / length - s * s / length(也就是误把 当成 ),第二项整整大了 倍。用示例 2 的 2 1 7 2 跑,三个切点算出来的方差和全是负数,被 max(0.0, ...) 压成 ,页面输出 0.000000,而正确答案是 6.888889。写之前先把 与 在纸上分清楚。
2. 分割点范围写成 range(0, n) 或 range(1, n + 1)
for k in range(1, n) 才是全部合法位置。写成 range(0, n) 时 会让左段长度变成 ,var(0, 0) 里 length = 0,s / length 直接抛 ZeroDivisionError;写成 range(1, n + 1) 则是右段长度为 ,同样除零。
3. 用 round(best, 6) 输出
round 只管四舍五入不管补零。示例 1 的最大值是 ,print(round(best, 6)) 输出 81.0,而题目要求的是 6 位小数 81.000000。判定用数值也好、按文本比也好,这一处都会被判错。