环形舱室切成 K 段使段长和方差最小。方差乘 K² 后只需最小化段长平方和:小 N 枚举断环起点做斜率优化 DP,大 N 的 K 只为 2 或 3,双指针逼近 S/K 切点。
OJ: roj
题目 ID: 1791
难度:提高+/省选-
标签:动态规划斜率优化环形DP二分双指针python
创建: 2026-10-08 03:16
更新: 2026-10-08 03:16
形式化题目
给定一个长度为
即方差最小值与
约束:
两个容易读漏的点:题面定义的"方差"没有除以
解法路线
本题的难度全部来自"数据规模分层":
| 层 | 适用约束 | 上一层瓶颈 | 本层用到的观察 |
|---|---|---|---|
| 暴力枚举 | —— | 切段代价只与段长和有关 | |
| 子任务解法 | 枚举所有切点组合是 |
转移可写成直线取最小,凸包优化 | |
| 正解 | 断环起点任意,无法整体 DP | 段数极少,最优切点必然贴着 |
正式主解为 main.cpp 与 main.py,两者同一套分层算法。
暴力解法
适用范围
思路
先做代数化简。注意
两端同乘
暴力就是枚举环上所有切点组合(
复杂度
枚举量
瓶颈
瓶颈在"切点组合数",而不是"每组算代价"。化简后单组代价可以
子任务解法:
适用范围
思路
化环为链:枚举断环起点。 环形问题是"切
对一条链设
把平方展开,把与
括号里是"一堆直线
举一个把转移写成表格的推演,取自样例 2(
| 最优 |
切点 |
|||
|---|---|---|---|---|
| 1 | 4 | 16 | ∞ | —— |
| 2 | 6 | 36 | 1 | |
| 3 | 12 | 144 | 2 | |
| 4 | 13 | 169 | 3 | |
| 5 | 16 | 256 | 3 |
表中
复杂度
时间
代码
与整体解法共用,见下文正解的 main.cpp / main.py 分支 N <= 400。
复杂度与瓶颈
瓶颈在
正解
关键观察
观察一:data.py 印证:大数据点的
观察二:
观察三:
思路
分三种情况写,全部复用一个倍长前缀和数组
:只有一段,方差恒为 0,直接输出 。 :如上一节的枚举断环起点 + 凸包斜率优化 DP,精确求解。 且 :双指针,对每个起点 取 与 两个切点算代价,精确。 且 :先双指针定第一个切点 (第一段权和 的最远点), 再在 上二分找第二个切点 (第二段权和 的最远点), 检查 三个候选。
最后统一套公式 long long 上限,所以 C++ 里用 __int128 计算;Python 整数天然无溢出。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 03:16
# update_at: 2026-10-08 03:16
import sys
INF = 4 * 10**18 # 上界:S <= 3e8 时 Σs_i^2 <= S^2 <= 9e16
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Hull = list[tuple[int, int]] # 下凸壳上的直线 y = m*x + b,斜率随下标严格递减
def hull_add(hull: Hull, m: int, b: int) -> None:
"""按斜率递减的顺序加入直线 y = m*x + b,弹掉被两头夹住、永不最优的中间线。"""
while len(hull) >= 2:
m1, b1 = hull[-2]
m2, b2 = hull[-1]
# line2 与 new 的交点不晚于 line1 与 line2 的交点 => line2 不在包上
if (b - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m):
hull.pop()
else:
break
hull.append((m, b))
def solve_ring_small(ring: list[int], n: int, k: int) -> int:
"""n <= 400:枚举 n 个断环起点,每层做单调凸包优化的 DP,求最小 Σs_i^2。
dp[i] = 前 i 个点分成当前层数的最小 Σs^2,转移 dp[i] = min_j dp[j] + (cur[i]-cur[j])^2;
展开得 cur[i]^2 + min_j ( -2*cur[j]*cur[i] + dp[j]+cur[j]^2 ),括号里是 x = cur[i] 处
一堆直线的最小值。x 单调不减、斜率 -2*cur[j] 单调递减,故查询指针只往右走,均摊 O(1)。
"""
best = INF
for d in range(n):
cur = [0] * (n + 1)
for i in range(1, n + 1):
cur[i] = cur[i - 1] + ring[d + i - 1] # 把环从 ring[d] 处断开后的前缀和
dp = [INF] * (n + 1)
dp[0] = 0
for _ in range(k):
hull: Hull = []
ptr = 0 # 当前 x 所对应的最优直线下标,随 x 增大只增不减
ndp = [INF] * (n + 1)
for i in range(1, n + 1):
j = i - 1
if dp[j] < INF:
hull_add(hull, -2 * cur[j], dp[j] + cur[j] * cur[j])
if hull:
x = cur[i]
if ptr >= len(hull):
ptr = len(hull) - 1
while ptr + 1 < len(hull) and (
hull[ptr + 1][0] * x + hull[ptr + 1][1]
<= hull[ptr][0] * x + hull[ptr][1]
):
ptr += 1
ndp[i] = hull[ptr][0] * x + hull[ptr][1] + x * x
dp = ndp
best = min(best, dp[n])
return best
def solve_ring_k2(pre: list[int], n: int, s: int) -> int:
"""n 大且 K=2:双指针维护权和最接近 S/2 的切点,O(n)。"""
best = INF
j = 1
for i in range(1, n + 1):
while j <= i + n - 2 and (pre[j + 1] - pre[i - 1]) * 2 <= s:
j += 1
for cut in (j, j + 1): # S/2 两侧各取一个切点
if cut < i or cut > i + n - 1:
continue
v = pre[cut] - pre[i - 1]
best = min(best, v * v + (s - v) * (s - v))
return best
def solve_ring_k3(pre: list[int], n: int, s: int) -> int:
"""n 大且 K=3:第一个切点取权和 <= S/3 的最远点,第二个切点用单调指针定位,O(n)。"""
best = INF
j = 1
l = 1
for i in range(1, n + 1):
while j <= i + n - 2 and (pre[j + 1] - pre[i - 1]) * 3 <= s:
j += 1
l = max(l, j + 1) # 第二段必须非空;j 递增 => 目标权和递增 => l 也单调不减
while l + 1 <= i + n - 1 and (pre[l + 1] - pre[j]) * 3 <= s:
l += 1
for k2 in (l - 1, l, l + 1): # 第二段权和在 S/3 两侧的候选
if k2 < j + 1 or k2 > i + n - 2:
continue
v1 = pre[j] - pre[i - 1]
v2 = pre[k2] - pre[j]
v3 = s - v1 - v2
if v3 > 0:
best = min(best, v1 * v1 + v2 * v2 + v3 * v3)
return best
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, k = next(data), next(data)
a = [next(data) for _ in range(n)]
ring = a + a # 倍长,供断环起点与任意区间和取用
pre = [0] * (2 * n + 1)
for i in range(1, 2 * n + 1):
pre[i] = pre[i - 1] + ring[i - 1]
s = pre[n] # 总长度
if k <= 1: # 只有一段,方差恒为 0
print(0)
return
if n <= 400:
min_sum_sq = solve_ring_small(ring, n, k)
elif k == 2:
min_sum_sq = solve_ring_k2(pre, n, s)
else:
min_sum_sq = solve_ring_k3(pre, n, s) # 大数据里 K 只可能是 3
print(k * k * min_sum_sq - k * s * s) # Python 整数无溢出,与 C++ 的 __int128 同义
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 03:16
* update_at: 2026-10-08 03:16
*/
// main.cpp:太空飞船(环形序列分成 K 段,最小化各段长度和的"方差")。
// 关键推导:方差 = Σ(s_i - S/K)^2,两边乘 K^2 得 K^2·Σs_i^2 - K·S^2,
// 于是只需最小化 Σs_i^2,答案 = K^2·minSumSq - K·S^2。
// 与 main.py 同一算法:n 小(<=400)枚举断环起点 + 凸包斜率优化 DP;
// n 大时 K 只可能是 2 或 3,分别用双指针 / 双指针 + 二分处理。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
const ll INF = (ll)4e18;
int N, K; // 舱室个数、要分成的段数
ll a[600005]; // 舱室长度;开两倍供断环使用(1-indexed)
ll pre[600005]; // 倍长前缀和:pre[i] = a[1..i] 之和
ll S; // 总长度 S = pre[N]
/* ==================== 小数据分支:枚举断环起点 + 斜率优化 ==================== */
ll cur_[405]; // 旋转后的前缀和(把环从 d 处断开)
ll dp[405], ndp[405]; // dp[i]:前 i 个点分成 t 段的最小 Σs^2
ll hm[405], hb[405]; // 凸包上的直线:y = hm*x + hb
int hsz; // 凸包大小
// 直线在 x 处的取值
inline ll fval(int id, ll x) { return hm[id] * x + hb[id]; }
// 加一条直线 y = m*x + b。斜率 m 按严格递减的顺序加入(m = -2*cur_[j]);
// 弹掉被两头夹住的中间直线,保持下凸壳。
void hullAdd(ll m, ll b) {
while (hsz >= 2) {
ll m1 = hm[hsz - 2], b1 = hb[hsz - 2];
ll m2 = hm[hsz - 1], b2 = hb[hsz - 1];
// 若 line1 与 new 的交点不晚于 line1 与 line2 的交点,则 line2 无用
if ((b - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m))
hsz--;
else
break;
}
hm[hsz] = m;
hb[hsz] = b;
hsz++;
}
// 凸包上取值关于下标单峰,二分找最小值
ll hullMin(ll x) {
int lo = 0, hi = hsz - 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (fval(mid, x) <= fval(mid + 1, x))
hi = mid;
else
lo = mid + 1;
}
return fval(lo, x);
}
// O(N·K) 斜率优化 DP:对每个断环起点都算一遍
ll solveSmall() {
ll best = INF;
for (int d = 1; d <= N; d++) {
cur_[0] = 0;
for (int i = 1; i <= N; i++) cur_[i] = cur_[i - 1] + a[d + i - 1];
dp[0] = 0;
for (int i = 1; i <= N; i++) dp[i] = INF;
for (int t = 1; t <= K; t++) {
hsz = 0;
for (int i = 1; i <= N; i++) {
int j = i - 1; // 先放入 j=i-1,保证查 i 时只用到 j < i
if (dp[j] < INF)
hullAdd(-2 * cur_[j], dp[j] + cur_[j] * cur_[j]);
ndp[i] = (hsz > 0) ? (hullMin(cur_[i]) + cur_[i] * cur_[i]) : INF;
}
for (int i = 0; i <= N; i++) dp[i] = ndp[i];
}
best = min(best, dp[N]);
}
return best;
}
/* ==================== 大数据分支 K = 2:双指针找最平衡切点 ==================== */
ll solveK2() {
ll best = INF;
int j = 1;
for (int i = 1; i <= N; i++) {
// j 单调不减:第一段权和不超过 S/2 的最远切点
while (j <= i + N - 2 && (pre[j + 1] - pre[i - 1]) * 2 <= S) j++;
for (int d = 0; d <= 1; d++) { // 切点 j / j+1 分别在 S/2 两侧
int cut = j + d;
if (cut < i || cut > i + N - 1) continue;
ll v = pre[cut] - pre[i - 1];
best = min(best, v * v + (S - v) * (S - v));
}
}
return best;
}
/* ============ 大数据分支 K = 3:先定第一个切点,再二分第二个切点 ============ */
ll solveK3() {
ll best = INF;
int j = 1;
for (int i = 1; i <= N; i++) {
// 第一个切点:第一段权和 <= S/3 的最远点 j
while (j <= i + N - 2 && (pre[j + 1] - pre[i - 1]) * 3 <= S) j++;
// 第二个切点:在 (j, i+N-2] 内找第二段权和 <= S/3 的最远右端点 l
int l = j + 1, r = i + N - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if ((pre[mid] - pre[j]) * 3 > S)
r = mid - 1;
else
l = mid;
}
// 第二段权和落在 S/3 左右两侧的候选都试一遍(保证三段非空)
for (int d = -1; d <= 1; d++) {
int k2 = l + d;
if (k2 < j + 1 || k2 > i + N - 2) continue;
ll v1 = pre[j] - pre[i - 1];
ll v2 = pre[k2] - pre[j];
ll v3 = S - v1 - v2;
if (v3 <= 0) continue;
best = min(best, v1 * v1 + v2 * v2 + v3 * v3);
}
}
return best;
}
int main() {
if (scanf("%d %d", &N, &K) != 2) return 0;
for (int i = 1; i <= N; i++) {
scanf("%lld", &a[i]);
a[i + N] = a[i];
}
for (int i = 1; i <= 2 * N; i++) pre[i] = pre[i - 1] + a[i];
S = pre[N];
if (K <= 1) { // 只有一段,方差恒为 0
printf("0\n");
return 0;
}
ll minSumSq;
if (N <= 400)
minSumSq = solveSmall(); // 精确 DP,K 可到 20
else if (K == 2)
minSumSq = solveK2(); // 精确双指针
else
minSumSq = solveK3(); // 大数据里 K 只可能是 3
lll ans = (lll)K * K * minSumSq - (lll)K * S * S; // __int128 防溢出
if (ans < 0) { // 理论上非负,防御性处理
putchar('-');
ans = -ans;
}
char buf[64];
int p = 0;
if (ans == 0) buf[p++] = '0';
while (ans > 0) {
buf[p++] = char('0' + (int)(ans % 10));
ans /= 10;
}
while (p > 0) putchar(buf[--p]);
putchar('\n');
return 0;
}复杂度
| 分支 | 时间 | 空间 |
|---|---|---|
瓶颈点是
总结
- 先化简再谈算法:方差乘
后只剩 一项依赖切法, 这一步把"求方差"变成"求最小平方和",是整题的地基。 - 化环为链有两条路:小数据枚举断环起点(
倍代价换回普通线性 DP), 大数据直接在两倍长前缀和上做双指针/二分(不枚举起点)。 - 按
分层是本题的题眼: 大必然 小, 大必然 小, 两处瓶颈不会叠加,所以可以放心写两套完全不同的代码。 - 候选切点要两侧都看:双指针只能停在
目标的那一侧, 必须同时检查 与 ( 时是 ),否则会漏掉更优解。
图示解析
下图展示
flowchart LR
subgraph ring["环(已从起点 i 展开成链)"]
A["第一段<br/>权和 <= S/3"] --> B["第二段<br/>定位到 S/3 附近"] --> C["第三段<br/>剩余权和"]
end
A -.->|"双指针 j"| B
B -.->|"二分 + 检查 l-1, l, l+1"| C
观察重点:三段权和一旦都在