把评价指数拆成 G[j] 乘前缀和,固定班数后断点项与 i 无关,用单调队列维护滑窗最小值,O(NM) 求出最小评价指数,再按班数、末班人数依次取优。
OJ: roj
题目 ID: 1789
难度:提高+/省选-
标签:动态规划单调队列python
创建: 2026-10-08 02:58
更新: 2026-10-08 02:58
形式化题目
给出
先把学生序列切成连续的若干段,从左到右第
求三元组
注意
正解
思路
第一步:把目标函数拆成"教室编号 × 区间权值和"。
第二步:写出朴素 DP 并看清瓶颈。
设
状态数是
第三步:把与
把上式展开:
第四步:单调队列把单次转移降到均摊
固定
第五步:处理三个目标的字典序。
:就是 的最小值,枚举 取最小即可。 :按 从小到大枚举,用严格小于更新最优值,这样 相同时自然保留最小的 。 :末班人数是 ,要让 小就要 大,也就是在窗口内取到最小价值时取最大的 。实现手法:入队时把队尾价值 (而不是 ) 新价值的候选弹掉, 平手时新点把旧点挤走,队首留下的就是"取到最小值且下标最大"的 。
下表是题面样例的
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 16 | 11 | 12 | 13 | 10 | 15 | 16 | 17 | 18 | 14 | |
| 1 | 16 | 9 | 4 | 25 | 0 | 1 | 4 | 9 | 1 | |
| 1 | 17 | 26 | 30 | 55 | 55 | 56 | 60 | 69 | 70 |
186 3 4 一致。用
代码
main.cpp 用单调队列实现,一层 j 一个滚动数组 prv -> cur。
/**
* 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++ 同阶(同样 collections.deque 存
(断点, 价值) 二元组:
#!/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()复杂度
- 时间:预处理
;DP 层数 ,每层 ,每层每个候选点 最多进队出队一次,合计 。单组数据 时约 次运算, 远快于 1000 ms。 - 空间:两个
的滚动数组加一个 的单调队列, 。 - 数值:
( ), , ,必须用 64 位整数,无穷大取 。
总结
- 见到
这样的转移,先把与 无关的项提出去, 剩下的就是一个"窗口 slid 取最小值"的裸结构。 - 字典序多目标优化有两种落地方式:外层用严格小于逐个更新,或者把次要指标跟主指标打包成 二元组一起比较。这里用了前者;末班人数则靠在单调队列的平手规则里偏向更大的断点解决。
- 本题的
可能为负(题面第 8–10 组 ), 最小化显然要挑最小的负系数,答案 可以为负,所以初值不能取 ,要取正无穷哨兵。 - 素材说明:本题素材源(
new_ROJ/problems/1789/)自带data.py数据生成脚本,data/是脚本按题面规模自造的而非官方测点,题面亦为网络重建;本地用该数据 10/10 通过, 但这不等价于官方 AC。std.cpp与本解法思路一致,其生成的锚点(如全等时 、 全负时压班数)也被本地实现复现。