分班

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

把评价指数拆成 G[j] 乘前缀和,固定班数后断点项与 i 无关,用单调队列维护滑窗最小值,O(NM) 求出最小评价指数,再按班数、末班人数依次取优。

OJ: roj

题目 ID: 1789

难度:提高+/省选-

标签:动态规划单调队列python

创建: 2026-10-08 02:58

更新: 2026-10-08 02:58

形式化题目

给出 MM 个已按分数降序排列的学生,敏感指数为 X[1..M]X[1..M],再给出 NN 个教室的舒适程度 G[1..N]G[1..N]。记

Average=⌊1M∑i=1MX[i]⌋,W[i]=(X[i]−Average)2.Average = \left\lfloor \frac{1}{M}\sum_{i=1}^{M} X[i] \right\rfloor, \qquad W[i] = (X[i] - Average)^2 .

先把学生序列切成连续的若干段,从左到右第 jj 段作为第 jj 个教室的学生,段数 kk 满足 1⩽k⩽N1 \leqslant k \leqslant N,且每段长度都落在 [A,B][A, B] 内。设 g[i]g[i] 表示第 ii 个学生被分到的教室 编号,则这个分班的评价指数为

σ=∑i=1M(X[i]−Average)2⋅G[g[i]]=∑j=1kG[j]⋅∑i∈第 j 段W[i].\sigma = \sum_{i=1}^{M} (X[i]-Average)^2 \cdot G[g[i]] = \sum_{j=1}^{k} G[j] \cdot \sum_{i \in \text{第 } j \text{ 段}} W[i] .

求三元组 (σ,class,last)(\sigma, class, last),按字典序最小:先让 σ\sigma 最小,再在 σ\sigma 最小的方案里 让班数 classclass 最小,最后在两者都最小的方案里让最后一个班的人数 lastlast 最小。

注意 AverageAverage 与 W[i]W[i] 只由 XX 决定,与怎么分班无关,所以它们是常数。

正解

思路

第一步:把目标函数拆成"教室编号 × 区间权值和"。

σ\sigma 只跟每个班的权值和(WW 的区间和)有关,于是先用前缀和把区间和变成两个前缀值之差。 记 P[i]=∑t⩽iW[t]P[i] = \sum_{t \leqslant i} W[t]、P[0]=0P[0]=0,那么第 jj 段 [k+1,i][k+1, i] 的贡献是 G[j]⋅(P[i]−P[k])G[j] \cdot (P[i]-P[k])。

第二步:写出朴素 DP 并看清瓶颈。

设 f[j][i]f[j][i] 表示前 ii 个学生恰好分成 jj 个班(每班人数在 [A,B][A,B] 内)的最小评价指数, 边界 f[0][0]=0f[0][0]=0,其余为 +∞+\infty。枚举上一段的右端点 kk:

f[j][i]=min⁡i−B⩽k⩽i−A(f[j−1][k]+G[j]⋅(P[i]−P[k])).f[j][i] = \min_{i-B \leqslant k \leqslant i-A} \Big( f[j-1][k] + G[j] \cdot (P[i]-P[k]) \Big).

状态数是 O(NM)O(NM),每个状态还要枚举 kk,最坏 O(M)O(M),总计 O(NM2)O(NM^2),M=104M=10^4 时不可接受。

第三步:把与 ii 无关的项提出去,看出滑动窗口。

把上式展开:

f[j][i]=G[j]⋅P[i]+min⁡i−B⩽k⩽i−A{f[j−1][k]−G[j]⋅P[k]}.f[j][i] = G[j] \cdot P[i] + \min_{i-B \leqslant k \leqslant i-A} \Big\{ f[j-1][k] - G[j] \cdot P[k] \Big\}.

G[j]⋅P[i]G[j] \cdot P[i] 对固定的 i,ji,j 是常数,可以提到 min⁡\min 外面;括号里只含 kk,与 ii 无关。 而 kk 的取值范围 [i−B,i−A][i-B, i-A] 随 ii 增大而区间两端一起右移,是标准的滑动窗口, 窗口宽度固定为 B−A+1B-A+1。

第四步:单调队列把单次转移降到均摊 O(1)O(1)。

固定 jj,从小到大枚举 ii:ii 每增加 11,就有一个新的 k=i−Ak=i-A 滑入窗口, 同时有 k<i−Bk<i-B 的旧点滑出。用一个队列存候选 kk,并保持 f[j−1][k]−G[j]⋅P[k]f[j-1][k]-G[j]\cdot P[k] 沿队列单调递增(队首即最小值),则入队、出队、查最小都是均摊 O(1)O(1)。每层 jj 只扫一遍 ii,总复杂度 O(NM)O(NM),滚动数组后空间 O(M)O(M)。

第五步:处理三个目标的字典序。

  • σ\sigma:就是 f[j][M]f[j][M] 的最小值,枚举 jj 取最小即可。
  • classclass:按 jj 从小到大枚举,用严格小于更新最优值,这样 σ\sigma 相同时自然保留最小的 jj。
  • lastlast:末班人数是 M−kM-k,要让 lastlast 小就要 kk 大,也就是在窗口内取到最小价值时取最大的 kk。实现手法:入队时把队尾价值 ⩾\geqslant(而不是 >>) 新价值的候选弹掉, 平手时新点把旧点挤走,队首留下的就是"取到最小值且下标最大"的 kk。

下表是题面样例的 WW 与前缀和(Average=152/10=15Average = 152/10 = 15,故 WW 序列为 1,16,9,4,25,0,1,4,9,11,16,9,4,25,0,1,4,9,1),P=0,1,17,26,30,55,55,56,60,69,70P = 0,1,17,26,30,55,55,56,60,69,70:

ii 1 2 3 4 5 6 7 8 9 10
X[i]X[i] 16 11 12 13 10 15 16 17 18 14
W[i]W[i] 1 16 9 4 25 0 1 4 9 1
P[i]P[i] 1 17 26 30 55 55 56 60 69 70

A=1,B=4A=1,B=4。最优划分是 [1,4],[5,6],[7,10][1,4],[5,6],[7,10]:$G[1]!\cdot!30 + G[2]!\cdot!25 + G[3]!\cdot!15 = 4\cdot30 + 5\cdot25 + 1\cdot15 = 120+125+15 = 186$,班数 33,末班 44 人, 与样例输出 186 3 4 一致。用 j=3j=3 举例:f[3][10]f[3][10] 需要在 k∈[6,9]k\in[6,9] 中取 f[2][k]−G[3]P[k]f[2][k]-G[3]P[k] 的最小值,其中 k=6k=6(即末班为 [7,10][7,10] 四人)使末班最长,正好给出 last=4last=4。

代码

main.cpp 用单调队列实现,一层 j 一个滚动数组 prv -> cur。

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 02:58
 * update_at: 2026-10-08 02:58
 */

#include <cstdio>

typedef long long ll;

const int MAXM = 10005;  // 学生数上限 10000,留一点余量
const int MAXN = 205;    // 班级数上限 200,留一点余量
const ll INF = 4000000000000000000LL; // 无穷大哨兵:答案上界约 1e17,4e18 既远离溢出又足够大

ll X[MAXM];   // 第 i 个学生的敏感指数 X[i]
ll G[MAXN];   // 第 j 个教室的舒适程度 G[j]
ll pre[MAXM]; // pre[i] = Σ_{t<=i} (X[t]-Average)^2,即偏离平方的前缀和

ll prv[MAXM]; // f[j-1][i]:前 i 个学生恰好分成 j-1 个班的最小评价指数
ll cur[MAXM]; // f[j][i]  :前 i 个学生恰好分成 j 个班的最小评价指数

// 单调队列:存候选断点 k 及其价值 val[k] = prv[k] - G[j]*pre[k],
// val 沿队列严格递增,故队首即窗口内最小价值。
struct Node {
    int k;    // 断点下标
    ll val;   // prv[k] - gj*pre[k]
};
Node q[MAXM];

// 由 prv[] 推出 cur[]:固定班数 j 时,转移式
//     f[j][i] = G[j]*pre[i] + min_{i-B <= k <= i-A} { prv[k] - G[j]*pre[k] }
// 中的取值只依赖 k,窗口随 i 滑动,用单调队列均摊 O(1) 求最小值。
// 返回 f[j][M](不可达时返回 INF);out_last_k 返回 f[j][M] 取到最小值时最大的断点 k。
ll layer(int j, ll gj, int M, int A, int B, int &out_last_k) {
    int head = 0, tail = -1;                 // 空队列
    int lo = j * A;                          // j 个班每班至少 A 人
    int hi = j * B < M ? j * B : M;           // j 个班每班至多 B 人,故 i <= j*B
    out_last_k = -1;
    for (int i = 0; i <= M; ++i) cur[i] = INF;
    for (int i = lo; i <= hi; ++i) {
        int k = i - A;                       // 本步新滑入窗口的断点
        if (prv[k] < INF) {
            ll val = prv[k] - gj * pre[k];
            // 相等也弹掉队尾:平手时保留更大的 k,好让最后一个班更小
            while (head <= tail && val <= q[tail].val) --tail;
            ++tail;
            q[tail].k = k;
            q[tail].val = val;
        }
        while (head <= tail && q[head].k < i - B) ++head; // 滑出窗口
        if (head > tail) continue;                        // 该 i 不可达
        int kb = q[head].k;
        cur[i] = prv[kb] + gj * (pre[i] - pre[kb]);
        if (i == M) out_last_k = kb;
    }
    return cur[M];
}

int main() {
    int ncase;
    if (scanf("%d", &ncase) != 1) return 0;
    while (ncase--) {
        int M, N, A, B;
        if (scanf("%d %d %d %d", &M, &N, &A, &B) != 4) break;

        ll sum = 0;
        for (int i = 1; i <= M; ++i) {
            scanf("%lld", &X[i]);
            sum += X[i];
        }
        for (int j = 1; j <= N; ++j) scanf("%lld", &G[j]);

        ll avg = sum / M; // 先全部加起来再整除,取下整
        pre[0] = 0;
        for (int i = 1; i <= M; ++i) {
            ll d = X[i] - avg;
            pre[i] = pre[i - 1] + d * d;
        }

        // 边界:0 个学生分成 0 个班,评价指数为 0
        for (int i = 0; i <= M; ++i) prv[i] = INF;
        prv[0] = 0;

        ll best = INF;
        int best_class = 0, best_last = 0;
        int limit = N < M / A ? N : M / A; // 每个班至少 A 人,班数不可能超过 M/A
        for (int j = 1; j <= limit; ++j) {
            int last_k = -1;
            ll value = layer(j, G[j], M, A, B, last_k);
            for (int i = 0; i <= M; ++i) prv[i] = cur[i]; // 滚动数组:本层结果留给下一层
            // 严格小于:先保评价指数最小,同价时保留更小的班数
            if (last_k >= 0 && value < best) {
                best = value;
                best_class = j;
                best_last = M - last_k; // 最后一个班的人数已被单调队列压到最小
            }
        }

        printf("%lld %d %d\n", best, best_class, best_last);
    }
    return 0;
}

Python 版与 C++ 同阶(同样 O(NM)O(NM)),只是把队列换成 collections.deque 存 (断点, 价值) 二元组:

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 02:58
# update_at: 2026-10-08 02:58

import sys
from collections import deque

INF = 4 * 10**18  # 无穷大哨兵:评价指数上界约 1e17,4e18 既远离溢出又足够大


def layer(prv: list[int], pre: list[int], gj: int, A: int, B: int, lo: int, hi: int) -> tuple[list[int], int]:
    """算出一层 DP:固定班数时前 i 人的最小评价指数,以及 f[M] 取到最小值时最大的断点。

    转移式 f[i] = gj*pre[i] + min{ prv[k] - gj*pre[k] }(k 取自 [i-B, i-A]),
    括号内只与 k 有关,窗口随 i 单调右移,故用单调队列均摊 O(1) 取最小值。
    """
    n = len(pre) - 1
    cur = [INF] * (n + 1)
    dq = deque()  # 候选断点及其价值 prv[k]-gj*pre[k],价值沿队列递增
    last_k = -1

    for i in range(lo, hi + 1):
        k = i - A  # 本步新滑入窗口的断点
        if prv[k] < INF:
            val = prv[k] - gj * pre[k]
            # 相等也弹掉队尾:平手时留下更大的 k,最后一个班就更小
            while dq and dq[-1][1] >= val:
                dq.pop()
            dq.append((k, val))
        while dq and dq[0][0] < i - B:  # 队首滑出窗口
            dq.popleft()
        if not dq:
            continue  # 该 i 不可达
        kb, valb = dq[0]
        cur[i] = valb + gj * pre[i]
        if i == n:
            last_k = kb

    return cur, last_k


def solve_case(M: int, N: int, A: int, B: int, X: list[int], G: list[int]) -> tuple[int, int, int]:
    """求一组数据的 (sigma, class, last):先压评价指数,再压班数,最后压末班人数。"""
    avg = sum(X) // M  # 先全部相加再整除,取下整
    pre = [0] * (M + 1)
    for i, v in enumerate(X, 1):
        pre[i] = pre[i - 1] + (v - avg) ** 2

    prv = [INF] * (M + 1)
    prv[0] = 0  # 边界:0 个学生分成 0 个班,评价指数为 0
    best, best_class, best_last = INF, 0, 0

    for j in range(1, min(N, M // A) + 1):  # 每班至少 A 人,班数不会超过 M//A
        cur, last_k = layer(prv, pre, G[j - 1], A, B, j * A, min(M, j * B))
        prv = cur  # 滚动数组:本层结果就是下一层的前驱
        # 严格小于:评价指数相同则保留更小的班数
        if last_k >= 0 and cur[M] < best:
            best, best_class, best_last = cur[M], j, M - last_k

    return best, best_class, best_last


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    ncase = next(data)
    out: list[str] = []

    for _ in range(ncase):
        M, N, A, B = next(data), next(data), next(data), next(data)
        X = [next(data) for _ in range(M)]
        G = [next(data) for _ in range(N)]
        out.append("%d %d %d" % solve_case(M, N, A, B, X, G))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

  • 时间:预处理 O(M)O(M);DP 层数 ⩽min⁡(N,M/A)\leqslant \min(N, M/A),每层 O(M)O(M),每层每个候选点 最多进队出队一次,合计 O(NM)O(NM)。单组数据 M=104,N=200M=10^4,N=200 时约 2×1062\times10^6 次运算, 远快于 1000 ms。
  • 空间:两个 O(M)O(M) 的滚动数组加一个 O(M)O(M) 的单调队列,O(M)O(M)。
  • 数值:W[i]⩽1010W[i] \leqslant 10^{10}(X[i]⩽105X[i]\leqslant10^5),P[i]⩽1014P[i] \leqslant 10^{14}, G[j]⋅P[i]⩽1017G[j]\cdot P[i] \leqslant 10^{17},必须用 64 位整数,无穷大取 4×10184\times10^{18}。

总结

  • 见到 min⁡k(f[k]+G⋅(P[i]−P[k]))\min_k \big( f[k] + G \cdot (P[i]-P[k]) \big) 这样的转移,先把与 ii 无关的项提出去, 剩下的就是一个"窗口 slid 取最小值"的裸结构。
  • 字典序多目标优化有两种落地方式:外层用严格小于逐个更新,或者把次要指标跟主指标打包成 二元组一起比较。这里用了前者;末班人数则靠在单调队列的平手规则里偏向更大的断点解决。
  • 本题的 GG 可能为负(题面第 8–10 组 −1000⩽G[i]⩽1000-1000 \leqslant G[i] \leqslant 1000), 最小化显然要挑最小的负系数,答案 σ\sigma 可以为负,所以初值不能取 00,要取正无穷哨兵。
  • 素材说明:本题素材源(new_ROJ/problems/1789/)自带 data.py 数据生成脚本, data/ 是脚本按题面规模自造的而非官方测点,题面亦为网络重建;本地用该数据 10/10 通过, 但这不等价于官方 AC。std.cpp 与本解法思路一致,其生成的锚点(如全等 XX 时 σ=0\sigma=0、 GG 全负时压班数)也被本地实现复现。