太空飞船

GitHub跳转原题关系图返回列表

环形舱室切成 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

形式化题目

给定一个长度为 NN 的环形序列 L1,L2,…,LNL_1, L_2, \dots, L_N(首尾相接),把它沿环切成 KK 段, 每段对应环上一段连续的舱室,各段长度和为 s1,…,sKs_1, \dots, s_K。记总长 S=∑LiS = \sum L_i、 平均段长 savg=S/Ks_{avg} = S / K,求

min⁡∑i=1K(si−savg)2⋅K2\min \sum_{i=1}^{K} \left(s_i - s_{avg}\right)^2 \cdot K^2

即方差最小值与 K2K^2 的乘积。

约束:1⩽Li⩽10001 \leqslant L_i \leqslant 1000,K⩽NK \leqslant N。

两个容易读漏的点:题面定义的"方差"没有除以 KK,就是 ∑(si−savg)2\sum (s_i - s_{avg})^2; 要求输出的又是它再乘 K2K^2,所以最终答案一定是个整数。

解法路线

本题的难度全部来自"数据规模分层":NN 很小时 KK 可以大到 20, 而 NN 很大(10510^5、3×1053 \times 10^5)时 KK 反而只有 2 或 3。 于是三层的瓶颈各不相同:小数据要处理高维分段,大数据要处理难以 O(1) 定位的切点。

层 适用约束 上一层瓶颈 本层用到的观察
暴力枚举 N⩽400N \leqslant 400、K⩽20K \leqslant 20 —— 切段代价只与段长和有关
子任务解法 N⩽400N \leqslant 400、K⩽20K \leqslant 20 枚举所有切点组合是 O(NK)O(N^K) 转移可写成直线取最小,凸包优化
正解 NN 大、K=2K = 2 或 33 断环起点任意,无法整体 DP 段数极少,最优切点必然贴着 S/KS/K

正式主解为 main.cpp 与 main.py,两者同一套分层算法。

暴力解法

适用范围

N⩽400N \leqslant 400 且 KK 较小,用于验证公式本身;枚举量随 KK 爆炸,只作为理解起点。

思路

先做代数化简。注意 S=∑siS = \sum s_i 是定值,与切法无关:

∑i=1K(si−savg)2=∑i=1Ksi2−2savg∑i=1Ksi+Ksavg2=∑i=1Ksi2−S2K. \sum_{i=1}^{K} (s_i - s_{avg})^2 = \sum_{i=1}^{K} s_i^2 - 2 s_{avg}\sum_{i=1}^{K} s_i + K s_{avg}^2 = \sum_{i=1}^{K} s_i^2 - \frac{S^2}{K}.

两端同乘 K2K^2:

K2∑i=1K(si−savg)2=K2∑i=1Ksi2−KS2.K^2 \sum_{i=1}^{K} (s_i - s_{avg})^2 = K^2 \sum_{i=1}^{K} s_i^2 - K S^2.

KK 与 SS 都是常量,所以目标等价于最小化 ∑si2\sum s_i^2, 最后再套 K2⋅minSumSq−KS2K^2 \cdot \text{minSumSq} - K S^2 输出即可。 用样例 1 验算:K=2K=2,切法 [2 6][1 3 4][2\,6][1\,3\,4] 得 s=8,8s = 8, 8, minSumSq=128\text{minSumSq} = 128,22×128−2×162=02^2 \times 128 - 2 \times 16^2 = 0 ✓。

暴力就是枚举环上所有切点组合(NN 个断环位置 ×\times 在剩下 N−1N-1 个缝里选 K−1K-1 个), 逐组算 ∑si2\sum s_i^2 取最小。

复杂度

枚举量 O(NK)O(N^K),N=400,K=20N = 400, K = 20 时完全不可行。

瓶颈

瓶颈在"切点组合数",而不是"每组算代价"。化简后单组代价可以 O(1)O(1) 求出, 所以只要把枚举过程改成 DP、再优化转移,就能同时解决小数据的高 KK。

子任务解法:N⩽400N \leqslant 400

适用范围

N⩽400N \leqslant 400(可以承受 O(N2K)O(N^2 K)),KK 最大到 20。

思路

化环为链:枚举断环起点。 环形问题是"切 KK 段",等价于先指定某条缝不被切开 (作为第 1 段的起点),再在剩下的链上切 K−1K-1 刀。于是枚举 NN 个断环位置 dd, 每次把序列旋转成长度 NN 的链 Ld,Ld+1,…L_d, L_{d+1}, \dots,做一次区间 DP,O(N)O(N) 种旋转取最小。

对一条链设 pre[i]=∑t⩽iLtpre[i] = \sum_{t \leqslant i} L_t,ft[i]f_t[i] 表示前 ii 个舱室分成 tt 段的 最小 ∑s2\sum s^2,则

ft[i]=min⁡0⩽j<i(ft−1[j]+(pre[i]−pre[j])2).f_t[i] = \min_{0 \leqslant j < i}\Big(f_{t-1}[j] + \big(pre[i] - pre[j]\big)^2\Big).

把平方展开,把与 jj 无关的 pre[i]2pre[i]^2 提到外面:

ft[i]=pre[i]2+min⁡j<i(−2 pre[j]⏟mj⋅pre[i]+ft−1[j]+pre[j]2⏟bj).f_t[i] = pre[i]^2 + \min_{j < i}\Big(\underbrace{-2\,pre[j]}_{m_j} \cdot pre[i] + \underbrace{f_{t-1}[j] + pre[j]^2}_{b_j}\Big).

括号里是"一堆直线 y=mjx+bjy = m_j x + b_j 在 x=pre[i]x = pre[i] 处取最小值", x=pre[i]x = pre[i] 单调不减、斜率 mj=−2 pre[j]m_j = -2\,pre[j] 单调递减,正是**斜率优化(凸包)**的标准形态: 维护一个下凸壳,查询时在下标上二分(或指针右移),每层转移 O(Nlog⁡N)O(N \log N)、 不带 log⁡\log 是 O(N)O(N),总 O(N2K)O(N^2 K)。

举一个把转移写成表格的推演,取自样例 2(K=3K = 3)的断环起点 dd,使链为 4,2,6,1,34, 2, 6, 1, 3,pre=0,4,6,12,13,16pre = 0, 4, 6, 12, 13, 16:

ii pre[i]pre[i] f1[i]f_1[i] 最优 f2[i]f_2[i] 切点 jj
1 4 16 ∞ ——
2 6 36 16+22=2016 + 2^2 = 20 1
3 12 144 36+62=7236 + 6^2 = 72 2
4 13 169 144+12=145144 + 1^2 = 145 3
5 16 256 min⁡(144+42, 169+32)=178\min(144+4^2,\,169+3^2)=178 3

表中 f1[i]=pre[i]2f_1[i] = pre[i]^2(一段就是整条前缀),f2f_2 之后再做一层得到 f3[5]f_3[5]。 注意 KK 层只需滚动两个数组,空间是 O(N)O(N)。

复杂度

时间 O(N2K)O(N^2 K):外层 NN 个断环起点,内层 KK 层转移、每层 O(N)O(N)(凸包查询二分则为 O(Nlog⁡N)O(N \log N))。 空间 O(N)O(N)。N=400,K=20N = 400, K = 20 时约 3.2×1063.2 \times 10^6,实测毫秒级。

代码

与整体解法共用,见下文正解的 main.cpp / main.py 分支 N <= 400。

复杂度与瓶颈

瓶颈在 O(N2K)O(N^2 K) 的常数上:NN 一旦到 10510^5, 单是 N2N^2 就已经 101010^{10},必须换方法。而题面数据里 NN 大的点 KK 只取 2 或 3, 这提示我们:大数据要按 KK 的具体值另做文章。

正解

关键观察

观察一:KK 大和 NN 大不会同时出现。 题面数据规模表里, N⩽400N \leqslant 400 的点 KK 可以到 20;N=105,3×105N = 10^5, 3 \times 10^5 的点 KK 只有 2 或 3。 (这一点被仓库素材里的生成脚本 data.py 印证:大数据点的 KK 也正是 2、3。)

观察二:K=2K = 2 时可双指针。 目标 ∑si2\sum s_i^2 在两段时等于 v2+(S−v)2v^2 + (S-v)^2, 它是 vv 的凸函数,在 v=S/2v = S/2 处最小。枚举第一段起点 ii 后,第一段权和 v=pre[j]−pre[i−1]v = pre[j] - pre[i-1] 随 jj 单调增,所以"权和不超过 S/2S/2 的最远切点 jj" 本身也随 ii 单调右移 —— 这正是双指针,O(N)O(N) 就能对每个起点取到 S/2S/2 两侧的两个切点。

观察三:K=3K = 3 时切点仍贴着 S/3S/3。 若三段分别为 v1,v2,v3v_1, v_2, v_3, 和固定为 SS,∑si2\sum s_i^2 在"三者尽量接近 S/3S/3"时最小。于是: 固定第一段权和不超 S/3S/3 的最远切点 jj 之后,第二、三段的分配就是个 K=2K=2 子问题, 继续用单调指针 + 二分把它压到 S/3S/3 附近,并检查切点左右各一格即可。

思路

分三种情况写,全部复用一个倍长前缀和数组 prepre(pre[i]=∑t⩽iL(t−1) mod N+1pre[i] = \sum_{t \leqslant i} L_{(t-1) \bmod N + 1}, 两倍长度以支持任意环上区间和):

  1. K=1K = 1:只有一段,方差恒为 0,直接输出 00。
  2. N⩽400N \leqslant 400:如上一节的枚举断环起点 + 凸包斜率优化 DP,精确求解。
  3. N>400N > 400 且 K=2K = 2:双指针,对每个起点 ii 取 jj 与 j+1j+1 两个切点算代价,精确。
  4. N>400N > 400 且 K=3K = 3:先双指针定第一个切点 jj(第一段权和 ⩽S/3\leqslant S/3 的最远点), 再在 (j, i+N−2](j,\ i+N-2] 上二分找第二个切点 ll(第二段权和 ⩽S/3\leqslant S/3 的最远点), 检查 l−1,l,l+1l-1, l, l+1 三个候选。

最后统一套公式 ans=K2⋅minSumSq−K⋅S2\text{ans} = K^2 \cdot \text{minSumSq} - K \cdot S^2。 K⩽20K \leqslant 20、S⩽3×108S \leqslant 3 \times 10^8 时 KS2K S^2 可达 1.8×10181.8 \times 10^{18}, 接近 long long 上限,所以 C++ 里用 __int128 计算;Python 整数天然无溢出。

代码

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

分支 时间 空间
K=1K = 1 O(N)O(N) O(N)O(N)
N⩽400N \leqslant 400 O(N2K)O(N^2 K) O(N)O(N)
N>400, K=2N > 400,\ K = 2 O(N)O(N) O(N)O(N)
N>400, K=3N > 400,\ K = 3 O(Nlog⁡N)O(N \log N) O(N)O(N)

瓶颈点是 N⩽400N \leqslant 400 的 O(N2K)O(N^2 K) 与大数据点的 log⁡\log(二分第二个切点), 在 N=3×105N = 3 \times 10^5、1 s 时限下都绰绰有余。

总结

  • 先化简再谈算法:方差乘 K2K^2 后只剩 ∑si2\sum s_i^2 一项依赖切法, 这一步把"求方差"变成"求最小平方和",是整题的地基。
  • 化环为链有两条路:小数据枚举断环起点(O(N)O(N) 倍代价换回普通线性 DP), 大数据直接在两倍长前缀和上做双指针/二分(不枚举起点)。
  • 按 KK 分层是本题的题眼:KK 大必然 NN 小,NN 大必然 KK 小, 两处瓶颈不会叠加,所以可以放心写两套完全不同的代码。
  • 候选切点要两侧都看:双指针只能停在 ⩽\leqslant 目标的那一侧, 必须同时检查 jj 与 j+1j+1(K=3K=3 时是 l−1,l,l+1l-1, l, l+1),否则会漏掉更优解。

图示解析

下图展示 K=3K = 3 时"切点贴着 S/3S/3"是怎么落到环上的:第一刀放在权和不超过 S/3S/3 的最远缝处,第二刀在剩下的区间里同法定位,被检查的三个切点候选只差一个舱室。

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

观察重点:三段权和一旦都在 S/3S/3 附近,∑si2\sum s_i^2 自动最小; 图中两条虚线分别标出第一刀和第二刀的定位方式, 它们都不需要遍历整个环,只依赖"权和随切点单调增"这一个性质。