任务安排2

形式化题目

$N$ 个任务按给定顺序排成一列。把序列切成若干连续的批次 $B_1,\dots,B_k$ （ $B_r$ 由若干相邻任务组成），机器从时刻 $0$ 开始依次加工各批。第 $r$ 批的加工时长

\text{len}(B_r)=S+\sum_{i\in B_r}T_i

其中 $S$ 是每批开始前的固定启动时间。同批任务在该批加工结束时同时完成，因此第 $r$ 批的完成时刻

e_r=\sum_{q=1}^{r}\text{len}(B_q)

任务 $i$ 的费用为 $e_{r(i)}\cdot C_i$ ，其中 $r(i)$ 是任务 $i$ 所属批次。求

\min_{\text{切分方案}}\ \sum_{r=1}^{k} e_r\sum_{i\in B_r}C_i

样例： $N=5$ 、 $S=1$ 、 $(T_i,C_i)$ 依次为 $(1,3),(3,2),(4,3),(2,3),(1,4)$ ，最优切分为 $B_1=\{1,2\},B_2=\{3,4\},B_3=\{5\}$ ，三批完成时刻为 $5,12,14$ ，总费用 $5\cdot 5+12\cdot 6+14\cdot 4=153$ 。

正解

思路

朴素做法的瓶颈：绝对时刻

设 $f[i]$ 为前 $i$ 个任务的最小总费用，枚举最后一批的起点 $j$ ：

f[i]=\min_{0\le j<i}\Big\{f[j]+\text{（最后一批的费用）}\Big\}

问题在于"最后一批的费用"= $e\cdot\sum_{i\in B}C_i$ ，而完成时刻 $e$ 是从时刻 0 起的绝对量：

e=\sum_{q\le r}\Big(S+\sum_{i\in B_q}T_i\Big)

它取决于前面所有批次的历史。若照原式转移，就必须在状态里额外记录"机器现在跑到第几秒"， $f[i]$ 一维装不下，DP 直接失效。所以瓶颈不是枚举量，而是记账方式。

关键观察：换记账次序

第一步：把完成时刻拆成“任务耗时前缀 + 启动时间”。 设第 $r$ 批的结束位置是 $e_r$ （ $e_0=0$ ），则

e_r=st[e_r]+S\cdot r

理由： $e_r=e_{r-1}+S+(st[e_r]-st[e_{r-1}])$ ，把 $e_{r-1}=st[e_{r-1}]+S(r-1)$ 代入即得。于是（记 $W_r=sc[e_r]-sc[e_{r-1}]$ 为第 $r$ 批的 $C$ 之和）

\text{total}=\sum_{r=1}^{k}e_r W_r=\underbrace{\sum_{r=1}^{k} st[e_r]\,W_r}_{A}+\underbrace{S\sum_{r=1}^{k} r\,W_r}_{B}

第二步：把 $B$ 也换成“每批一次”的形式。 两边双重计数： $B$ 把每个任务的 $C_i$ 算 $r(i)$ 次；而 $\sum_{r}(SC-sc[e_{r-1}])$ 对每个任务 $i$ 也在满足 $e_{r-1}<i$ 的那些 $r$ 上各算一次，恰好也是 $r(i)$ 次。所以

B=S\sum_{r=1}^{k}\bigl(SC-sc[e_{r-1}]\bigr)

这一步是整个推导的关键： $r$ （第几批）这个全局信息，被换成了 $e_{r-1}$ 这个局部信息。现在每一批的贡献只与它自己的左右端点 $e_{r-1},e_r$ 有关：

\text{第 }r\text{ 批}\;(j,i]\;\text{的贡献}=st[i]\cdot\bigl(sc[i]-sc[j]\bigr)+S\cdot\bigl(SC-sc[j]\bigr)

前半段是“这段任务的耗时由这段任务的 $C$ 支付”，后半段是“本批的启动时间 $S$ ，由本批及其后所有还在等待的任务共同支付”。于是

f[i]=\min_{0\le j<i}\Big\{f[j]+st[i]\bigl(sc[i]-sc[j]\bigr)+S\bigl(SC-sc[j]\bigr)\Big\},\qquad f[0]=0

答案是 $f[N]$ 。

注意 $f[i]$ 的含义：它是“把上述 $A+B$ 记账截断到前 $i$ 个任务”时的最小值，不等于 “前 $i$ 个任务单独作为一道题的答案”（因为 $B$ 用的是全局的 $SC$ ）。这不影响正确性：对任何一个完整分批方案， $A+B$ 都恰好等于它的真实费用（第一步是恒等变形，第二步是双重计数），而 $i=N$ 时递推枚举了全部方案的这一记账值，所以 $f[N]$ 就是最小总费用。

以样例最优分批 $B_1=\{1,2\},B_2=\{3,4\},B_3=\{5\}$ 为例（ $S=1$ ， $SC=15$ ）：

批次	区间	$st[e_r]$	$W_r$	$A$ 的贡献	$S(SC-sc[e_{r-1}])$	$B$ 的贡献	小计
1	$(0,2]$	4	5	$4\times 5=20$	$15$	15	35
2	$(2,4]$	10	6	$10\times 6=60$	$15-5=10$	10	70
3	$(4,5]$	11	4	$11\times 4=44$	$15-11=4$	4	48
合计			15	124		29	153

两个恒等式在这里对上了： $A+B=124+29=153$ 就是真实总费用；而 $B$ 的两种算法也相等， $15+10+4=29=1\times 5+2\times 6+3\times 4$ 。注意逐批拆开看时 $A$ 列 $+B$ 列 $\ne e_rW_r$ （例如第 1 批： $20+15=35\ne 5\times 5$ ）——两者只保证总和相等： $A$ 把该批耗时算在该批的 $C$ 上， $B$ 把 $S$ 摊给它及其后所有任务，两部分合起来才是 $e_rW_r$ 的总和。 $B$ 这一列正是“启动时间被其后所有任务分担”的具体体现。于是问题变成 $O(N^2)$ 的线性 DP。

从转移式到直线族

把括号展开，并按 $j$ 的线性函数归并：

\begin{aligned} f[i]&=\min_{j<i}\Big\{f[j]+st[i]\bigl(sc[i]-sc[j]\bigr)+S\bigl(SC-sc[j]\bigr)\Big\}\\ &=st[i]\cdot sc[i]+S\cdot SC+\min_{0\le j<i}\Big\{\underbrace{\big(-sc[j]\big)}_{m_j}\cdot\underbrace{\big(st[i]+S\big)}_{x_i}+\underbrace{f[j]}_{b_j}\Big\} \end{aligned}

前两项 $sc[i]st[i]+S\cdot SC$ 与 $j$ 无关，可以整个移出 $\min$ 。剩下的部分说明：

每个历史决策 $j$ 对应平面中的一条直线 $y=m_jx+b_j$ ；求 $f[i]$ 就是问"所有已插入的直线在 $x=x_i$ 处的最小值"。

这是个标准几何问题，且本题有两条单调性可以利用：

单调性	来源	作用
插入斜率 $m_j=-sc[j]$ 严格递减	$C_j\ge 1\Rightarrow sc$ 严格递增	新直线只需与凸壳尾部维护凸性
查询横坐标 $x_i=st[i]+S$ 严格递增	$T_i\ge 1\Rightarrow st$ 严格递增	最优点在凸壳上单调右移，队首可直接弹出

因此用 collections.deque 维护所有直线的下凸壳即可，插入与查询都均摊 $O(1)$ ，总复杂度 $O(N)$ 。

样例推演

样例的前缀和（ $S=1$ ，故 $x_i=st[i]+1$ ； $SC=15$ ）：

$i$	1	2	3	4	5
$T_i$	1	3	4	2	1
$C_i$	3	2	3	3	4
$st[i]$	1	4	8	10	11
$sc[i]$	3	5	8	11	15

下表每一行是算法的一轮。"各候选 $j$ 的值"列出 $\min$ 花括号里那个量 $m_jx_i+b_j$ 对所有 $j<i$ 的取值（用于说明为什么队列里只剩少数几条直线），"最优 $j$ "是取到最小值的决策；最后一列的 $f[i]$ 按 $f[i]=st[i]sc[i]+S\cdot SC+\min$ 算出。

$i$	$st[i]$	$sc[i]$	$x_i$	各候选 $j$ 的值	最优 $j$	$f[i]$
1	1	3	2	$j{=}0$ : 0	0	18
2	4	5	5	$j{=}0$ : 0， $j{=}1$ : 3	0	35
3	8	8	9	$j{=}0$ : 0， $j{=}1$ : $-9$ ， $j{=}2$ : $-10$	2	69
4	10	11	11	$j{=}0$ : 0， $j{=}1$ : $-15$ ， $j{=}2$ : $-20$ ， $j{=}3$ : $-19$	2	105
5	11	15	12	$j{=}0$ : 0， $j{=}1$ : $-18$ ， $j{=}2$ : $-25$ ， $j{=}3$ : $-27$ ， $j{=}4$ : $-27$	3	153

例如 $i=5$ 时， $st[5]sc[5]+S\cdot SC=165+15=180$ ，加上最小值 $-27$ 得 $f[5]=153$ ，与题面输出一致；取到最优的 $j=3$ 表示最后一批是任务 $\{4,5\}$ 。

表里能直接看到两条单调性： $x_i=2,5,9,11,12$ 一路递增；而 $j$ 的值随 $i$ 增大被越来越新的决策压过（ $j=0$ 只在 $i=1,2$ 最优），这正是"队首一旦被后一条直线超过就永久弹出"的依据。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <cstdio>
#include <deque>
using namespace std;

typedef long long ll;
typedef __int128 lll; // 叉积可能超过 long long 范围，用 128 位

const int MAXN = 300005;

ll task_time[MAXN]; // 第 i 个任务的执行时间 T_i
ll task_cost[MAXN]; // 第 i 个任务的费用系数 C_i
ll n, s;

deque<pair<ll, ll> > hull; // 下凸壳上的直线 (斜率 m, 截距 b)，斜率随插入递减

// 128 位乘法：参数直接声明成 128 位，靠隐式转换避免出现强制转换
lll mul(lll a, lll b) { return a * b; }

// 把直线 y = m*x + b 压入凸壳尾部。
// 若队尾直线在新直线与次队尾直线的交点之上（三点不再构成下凸），它永远取不到最小值，弹掉。
void push_line(ll m, ll b) {
    while (hull.size() >= 2) {
        ll m1 = hull[hull.size() - 2].first, b1 = hull[hull.size() - 2].second;
        ll m2 = hull[hull.size() - 1].first, b2 = hull[hull.size() - 1].second;
        if (mul(b2 - b1, m2 - m) < mul(b - b2, m1 - m2)) break; // 队尾仍是凸壳顶点
        hull.pop_back();
    }
    hull.push_back(make_pair(m, b));
}

// 查询所有已插入直线在 x 处的最小值。
// 查询点 x 严格递增，最优直线沿凸壳单调右移，队首弹出即可均摊 O(1)。
ll min_line(ll x) {
    while (hull.size() >= 2
           && hull[0].first * x + hull[0].second >= hull[1].first * x + hull[1].second)
        hull.pop_front();
    return hull[0].first * x + hull[0].second;
}

int main() {
    scanf("%lld%lld", &n, &s); // S 是每批任务开始前的启动时间
    ll total_cost = 0;
    for (ll i = 1; i <= n; i++) {
        scanf("%lld%lld", &task_time[i], &task_cost[i]);
        total_cost += task_cost[i];
    }
    // f[i]：前 i 个任务的最小总费用（已把启动时间折算给「它及之后所有任务」）
    // f[i] = sc[i]*st[i] + S*total_cost + min_j { -sc[j]*(st[i]+S) + f[j] }
    // 每个决策 j 是一条斜率 -sc[j] 递减的直线，查询点 st[i]+S 递增 → 单调队列凸壳
    ll dp = 0, st = 0, sc = 0; // dp = f[0] = 0
    for (ll i = 1; i <= n; i++) {
        push_line(-sc, dp); // 此刻 sc、dp 仍是第 i-1 轮的值
        st += task_time[i];
        sc += task_cost[i];
        dp = sc * st + s * total_cost + min_line(st + s);
    }
    printf("%lld\n", dp);
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#!/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-01 21:44
# update_at: 2026-10-01 21:58

import sys
from collections import deque


def push_line(hull: deque[tuple[int, int]], m: int, b: int) -> None:
    """把直线 y = m*x + b 压入下凸壳的尾部（插入斜率 m 随插入递减）。

    凸壳只保留"可能成为最小值"的直线：若队尾直线在新直线与次队尾直线的
    交点之上（三点不再构成下凸），它永远取不到最小值，直接弹掉。
    """
    while len(hull) >= 2:
        (m1, b1), (m2, b2) = hull[-2], hull[-1]
        if (b2 - b1) * (m2 - m) < (b - b2) * (m1 - m2):
            break  # 队尾仍是凸壳顶点
        hull.pop()
    hull.append((m, b))


def min_line(hull: deque[tuple[int, int]], x: int) -> int:
    """查询所有已插入直线在 x 处的最小值。

    查询点 x = 前缀时间和 + S 严格递增，所以最优直线沿凸壳单调右移，
    用队首指针（这里是 popleft）均摊 O(1) 即可，不必二分。
    """
    while len(hull) >= 2 and hull[0][0] * x + hull[0][1] >= hull[1][0] * x + hull[1][1]:
        hull.popleft()
    m, b = hull[0]
    return m * x + b


def solve() -> None:
    read = sys.stdin.buffer.readline
    n, S = int(read()), int(read())               # S 是每批任务开始前的启动时间
    times: list[int] = []                         # 第 i 个任务的执行时间 T_i
    costs: list[int] = []                         # 第 i 个任务的费用系数 C_i
    for _ in range(n):
        t, c = map(int, read().split())
        times.append(t)
        costs.append(c)
    total_c = sum(costs)

    # f[i]：前 i 个任务的最小总费用（已把启动时间折算给"它及之后所有任务"）
    # 转移展开后 f[i] = sc[i]*st[i] + S*total_c + min_j { -sc[j]*(st[i]+S) + f[j] }
    # 每个决策 j 是一条斜率 -sc[j] 递减的直线，查询点 st[i]+S 递增 → 单调队列凸壳
    hull: deque[tuple[int, int]] = deque()
    dp = st = sc = 0                              # dp = f[0] = 0
    for t, c in zip(times, costs):
        push_line(hull, -sc, dp)                  # 此刻 sc、dp 仍是第 i-1 轮的值
        st += t
        sc += c
        dp = sc * st + S * total_c + min_line(hull, st + S)
    print(dp)


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(N)$ 。每个决策点入队、出队各至多一次，插入与查询均摊 $O(1)$ ；前缀和随读入滚动累加，也是 $O(N)$ 。对照朴素转移 $O(N^2)$ ， $N=3\times10^5$ 时不可行。
空间复杂度： $O(N)$ ，最坏情况下单调队列要存下全部 $N$ 条直线（例如 $C_i$ 很小、凸壳几乎不弹尾时）。实测 $N=3\times10^5$ 、 $T_i=C_i=512$ 时运行 0.25s、峰值内存约 45MB（限时 1000ms / 128MB）。

总结

换记账方式是本题的分水岭。完成时刻是绝对量，直接 DP 需要多记一维时间；用 $e_r=st[e_r]+S\cdot r$ 把费用拆为 $A+B$ ，再用双重计数把 $S\sum_r rW_r$ 换成 $S\sum_r(SC-sc[e_{r-1}])$ ，全局的“第几批”就消失了。
改写后的物理含义很直白：第 $r$ 批的贡献分两半——这段任务自己的耗时按自己的 $C$ 支付，而启动时间 $S$ 由本批及其后所有还在等待的任务共同支付。
得到 $f[i]=\min_j\{f[j]+st[i](sc_i-sc_j)+S(SC-sc_j)\}$ 后，展开并分离变量就变成 “每个 $j$ 一条直线，问 $x_i=st[i]+S$ 处的最小值”，即下凸壳求切点。
两条单调性决定用单调队列而非二分：斜率 $-sc[j]$ 递减、查询点 $st[i]+S$ 递增，两个方向都单调，于是队尾维护凸性、队首弹出失效直线，均摊 $O(1)$ 。
凸性判定务必用交叉相乘而不是除法： $\frac{b_2-b_1}{m_1-m_2}$ 与 $\frac{b-b_2}{m_2-m}$ 的大小比较两边同乘正的分母即可，避免浮点误差。
若题目允许 $T_i=0$ 或 $C_i=0$ ，两条单调性会退化（相等斜率 / 相等查询点），那时需要改用二分查找切点或 Li Chao 树。

图示解析

下面这张图串起本题从建模到得到答案的主线，每个节点是一个推理结论：

text

1
2
3
4
5
6
7
8
9N 个任务切成连续批次，同批同时完成
`- 直接 DP 的障碍：完成时刻是绝对量，状态要带一维时间
   `- 拆 e_r = st[e_r] + S*r ，并把 S*Σ r*W_r 双重计数成 S*Σ(SC-sc[e_{r-1}])
      `- 得到 O(N^2) 转移：f[i] = min_j { f[j] + st[i](sc[i]-sc[j]) + S(SC-sc[j]) }
         `- 展开并分离变量：每个 j 是一条直线 y = (-sc[j])x + f[j]
            `- 两条单调性：斜率递减 + 查询点递增
               |- 队尾：交叉相乘判下凸，弹掉不再最优的直线
               `- 队首：x 增大时直接弹掉被超越的直线
                  `- 均摊 O(1) 查询 -> 总复杂度 O(N)

先看第 2 个节点——它解释了为什么不能照搬"最后一批"的朴素转移；再看第 3 个节点，这是唯一需要一点代数技巧的地方，它把全局的批次序号换成了局部的区间端点。从第 4 个节点往后，每一步都只是把同一个 $\min$ 重新表达成几何语言，最后落到单调队列这个实现手段。

目录