食堂打饭

形式化题目

有 $N$ 个任务 $(a_i, b_i)$ ： $a_i$ 为加工时间， $b_i$ 为加工完成之后不占机器的后续时长。有两台完全相同的串行机器，每个任务必须在一台机器上加工完成，之后立即开始 $b_i$ 时长的后续过程。安排任务到两台机器，以及每台机器上的加工顺序，使"最后一个任务的后续过程结束时刻"最小，输出该最小值。

思路

一句话本质：队内顺序与窗口分配可以分离——单窗口内按 $b$ 降序排队可证最优（相邻交换论证），于是全体按 $b$ 降序排序后，问题退化为"每人进 1 号窗口还是 2 号窗口"的 0/1 分配，用背包式 DP（状态 = 1 号窗口累计打饭时间）求出最小完成时间。

先看一个不做任何优化的朴素解，它直接枚举所有方案：

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com 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-08-28 21:52
 * update_at: 2026-08-28 21:52
 */
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 完全不用任何贪心结论，直接枚举所有方案：
//   1) 01 序列 choose[] 枚举每个人分到 1 号窗口还是 2 号窗口；
//   2) 叶子节点里，对每个窗口内部的所有排队顺序（全排列）都试一遍。
// 取所有方案里"最后吃完时刻"的最小值，这就是最优答案。
// 复杂度约 O(2^N * (N+1)! * N)，只适合 N <= 8 的小数据。

const int MAXN = 10;
const int INF = 0x3f3f3f3f;

int n;
int a[MAXN], b[MAXN];   // 输入：打饭耗时、吃饭耗时
int choose[MAXN];       // choose[i] = 0/1 表示第 i 人分到 1 号 / 2 号窗口
int ans;

// 计算一个窗口内的人按 ids 给出的顺序排队时，最晚吃完的时刻。
int calc_one_window(int ids[], int cnt) {
    int cur = 0; // 窗口累计打饭时间
    int mx = 0;  // 该窗口最晚吃完时刻
    for (int k = 0; k < cnt; k++) {
        int id = ids[k];
        cur += a[id];          // 第 id 人打完饭的时刻
        mx = max(mx, cur + b[id]);
    }
    return mx;
}

// 叶子节点：当前 choose[] 已把所有人分好窗口，再枚举每个窗口内部的全排列。
void check() {
    int w1[MAXN], w2[MAXN];
    int c1 = 0, c2 = 0;
    for (int i = 1; i <= n; i++) {
        if (choose[i] == 0) w1[c1++] = i;
        else w2[c2++] = i;
    }
    sort(w1, w1 + c1); // 从任意固定顺序开始做全排列
    sort(w2, w2 + c2);
    do {
        do {
            int cur = max(calc_one_window(w1, c1), calc_one_window(w2, c2));
            if (cur < ans) ans = cur;
        } while (next_permutation(w2, w2 + c2));
    } while (next_permutation(w1, w1 + c1));
}

// 每一层决定第 dep 个人分到哪个窗口，dep == n+1 时得到一条完整 01 序列。
void dfs(int dep) {
    if (dep == n + 1) {
        check();
        return;
    }
    for (int v = 0; v <= 1; v++) { // 这一层选择第 dep 人的窗口
        choose[dep] = v;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }

    ans = INF;
    dfs(1);

    cout << ans << '\n';
    return 0;
}

这个暴力把问题看成两段选择序列：choose[i] = 0/1 决定第 i 人进 1 号还是 2 号窗口；叶子节点再对每个窗口内部的排队顺序做全排列。它枚举了"所有分法 × 所有队内顺序"，答案一定正确，但复杂度约 $O(2^N \cdot (N+1)! \cdot N)$ ，只适合 $N \leqslant 8$ 的小数据。

问题？ 分队、两条队各自的顺序三个自由度缠在一起，先处理哪一个？

先固定"谁在哪个窗口"，只看单条窗口内部。窗口串行打饭，一个人的吃完时刻 = 他前面所有人的打饭时间之和（前缀和）+ $a_i + b_i$ 。所以单窗口的目标是：给一串 $(a_i, b_i)$ 排顺序，使 $\max(\text{前缀和} + b_i)$ 最小。

问题？ 单窗口里两个相邻的人顺序"反了"，会不会更差？

用交换论证。设相邻两人 $i, j$ 满足 $b_i < b_j$ 且 $i$ 在前，两人 $a$ 分别为 $A, B$ ，前面共同前缀和为 $P$ ：

排队顺序	$i$ 的吃完时刻	$j$ 的吃完时刻
$i$ 在前	$P + A + b_i$	$P + A + B + b_j$
$j$ 在前	$P + A + B + b_i$	$P + B + b_j$

交换后两个时刻都不超过交换前的最大值（ $P + B + b_j \leqslant P + A + B + b_j$ 因 $A \geqslant 0$ ； $P + A + B + b_i \leqslant P + A + B + b_j$ 因 $b_i < b_j$ ），而两人前后所有人的时刻都不变（窗口累计打饭总量不变）。所以" $b$ 小者在前"的逆序交换不劣，反复交换后，每个窗口内部按 $b$ 降序最优。 $b$ 相等时两种顺序完全等价，不影响结论。

问题？ 两个窗口都要 $b$ 降序，怎么统一处理？

对全体按 $b$ 降序排序。任何窗口的人都是全体序列的子序列，子序列自动保持 $b$ 降序，所以每个窗口内部直接按"全局排序后的编号"从小到大排队即可——队内顺序这个自由度被完全消掉，剩下唯一决策：每人进哪个窗口。

问题？ 窗口分配还有 $2^N$ 种， $N = 500$ 怎么压？

注意到关键结构：按全局顺序处理到第 $i$ 人时，他进哪个窗口都排在该窗口队尾，因此他的吃完时刻只依赖"该窗口当前的累计打饭时间"。两个窗口累计打饭时间之和恒等于前缀和 $s_i$ ，所以只要记录 1 号窗口的累计打饭时间 $j$ ，2 号窗口的累计打饭时间 $s_i - j$ 就确定了——一维信息描述两边的状态。

问题？ 状态和转移具体怎么定？

设 $s_i$ 为前 $i$ 人 $a$ 的前缀和， $f_{i,j}$ 表示考虑前 $i$ 人、1 号窗口累计打饭时间为 $j$ 时，前 $i$ 人中最晚吃完时刻的最小值。第 $i$ 人只有两条路：

进 1 号窗口（需 $j \geqslant a_i$ ）：他打完饭的时刻就是 $j$ （含他），吃完时刻 $j + b_i$ ，从 $f_{i-1,j-a_i}$ 继承： $f_{i,j} \leftarrow \max(f_{i-1,j-a_i},\ j + b_i)$ ；
进 2 号窗口：2 号窗口累计打饭 $s_i - j$ ，吃完时刻 $(s_i - j) + b_i$ ，从 $f_{i-1,j}$ 继承： $f_{i,j} \leftarrow \max(f_{i-1,j},\ (s_i - j) + b_i)$ 。

两者取 min。初始 $f_{0,0} = 0$ ，其余 $+\infty$ 。答案 $= \min_j f_{N,j}$ 。转移只依赖上一层，滚动数组压掉第一维； $j$ 从大到小遍历保证 $f[j - a_i]$ 仍是上一层的值（标准 0/1 背包写法）。

样例 DP 表格

这张表用题面样例 5 人 $(2,2)(7,7)(1,3)(6,4)(8,5)$ （按 $b$ 降序后为 $(7,7),(8,5),(6,4),(1,3),(2,2)$ ），展示关键列 $j \in \{0,6,7,8,13,14,15\}$ 的 $f_{i,j}$ （ $\infty$ 表示该状态不可达）：

$i \backslash j$	0	6	7	8	13	14	15
0	0	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
1	14	$\infty$	14	$\infty$	$\infty$	$\infty$	$\infty$
2	20	$\infty$	14	14	$\infty$	$\infty$	20
3	25	20	18	17	17	18	20
4	25	20	18	17	17	17	18
5	26	20	19	18	17	17	17

看两个具体转移：第 3 行 $f_{3,8} = 17$ 来自 $f_{2,8} = 14$ 与"第 3 人进 2 号窗口、吃完时刻 $(21-8)+4 = 17$ "取 max——1 号窗口只有 $(8,5)$ （吃完 13），2 号窗口 $(7,7),(6,4)$ 最晚吃完 17。第 5 行 $f_{5,13} = \max(f_{4,13}, (24-13)+2) = \max(17, 13) = 17$ ——第 5 人进 2 号窗口，其中 $f_{4,13} = 17$ 来自 1 号窗口内 $(7,7),(6,4)$ 依次打饭（吃完时刻 14、17）。最后一行对 $j$ 取 min 得答案 17，对应最优划分：1 号窗口 $(7,7),(6,4)$ ，2 号窗口 $(8,5),(1,3),(2,2)$ ，两窗口最晚吃完时刻分别是 17 和 13。

代码

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
67
68
69
70
71
72
73
74/**
 * 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-08-28 21:52
 * update_at: 2026-08-28 21:52
 */
#include <bits/stdc++.h>
using namespace std;

// D. 食堂(Meal)
// 思路：
// 1) 每个窗口内部按 b 降序排队最优（相邻交换论证），所以全局按 b 降序排序后，
//    任意窗口的队列（子序列）自动保持 b 降序，队内顺序这一自由度被消掉。
// 2) 剩下唯一决策：每人进 1 号窗口还是 2 号窗口。
//    按 b 降序依次处理每个人 i，此时第 i 人进某窗口一定排在该窗口队尾，
//    其吃完时刻 = 该窗口累计打饭时间 + b[i]。
// 3) 背包式 DP：f[j] 表示处理完当前前缀后、1 号窗口累计打饭时间为 j 时，
//    已经处理的这些人里最晚吃完时刻的最小值。
//    转移（第 i 人，s_i 为 a 的前缀和）：
//      - 进 1 号窗口：f[j] = min(f[j], max(f[j-a[i]], j + b[i]))
//      - 进 2 号窗口：f[j] = max(f[j], (s_i - j) + b[i])
//    答案 = min f[j]。

const int MAXN = 505;
const int INF = 0x3f3f3f3f;

struct Person {
    int a, b; // 打饭耗时、吃饭耗时
} p[MAXN];

int n;
int f[250005]; // 滚动数组：1 号窗口累计打饭时间为 j 时的最小"最晚吃完时刻"

bool cmp(const Person &x, const Person &y) {
    return x.b > y.b; // 按 b 降序
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].a >> p[i].b;
    }

    sort(p + 1, p + n + 1, cmp);

    memset(f, 0x3f, sizeof(f));
    f[0] = 0;

    int s = 0; // a 的前缀和
    for (int i = 1; i <= n; i++) {
        s += p[i].a;
        // j 从大到小：保证下面的 f[j - p[i].a] 还是上一层的值（0/1 背包式）
        for (int j = s; j >= 0; j--) {
            // 第 i 人进 2 号窗口：2 号窗口累计打饭 = s - j
            f[j] = max(f[j], s - j + p[i].b);
            // 第 i 人进 1 号窗口：打完饭时刻 = j，吃完时刻 = j + b[i]
            if (j >= p[i].a) {
                f[j] = min(f[j], max(f[j - p[i].a], j + p[i].b));
            }
        }
    }

    int ans = INF;
    for (int j = 0; j <= s; j++) {
        ans = min(ans, f[j]);
    }
    cout << ans << '\n';

    return 0;
}

复杂度

排序： $O(N \log N)$ 。
DP：第 $i$ 轮内层循环 $s_i+1$ 次（含 $j=0$ ），总迭代 $\sum (s_i+1) \leqslant N \cdot V$ ，其中 $V = \sum a_i \leqslant 250000$ 。即 $O(NV)$ ，最坏全部 $a_i = 500$ 时约 $6.3 \times 10^7$ 次迭代（上界 $1.25 \times 10^8$ ），实测 < 0.2s。
空间：滚动数组 $O(V)$ 。

注：官方 sol.md 写的 $O(n^2V)$ 不严谨——若 $V$ 指 $\sum a$ ，正确应为 $O(nV)$ ： $\sum_{i=1}^{N} s_i = \sum_{k} a_k (N-k+1) \leqslant N \cdot V$ （ $V=\sum a$ ）。推导详见过程文档 04。

总结

本题的思考路线是"先消自由度，再压状态"：

单窗口内用交换论证证明 $b$ 降序最优（这是带后续时长的单机调度的经典 Jackson 规则）；
全局排序后队内顺序自动确定， $2^N$ 种分法用背包式 DP 压缩；
DP 的状态设计利用了"第 $i$ 人总是队尾，吃完时刻只依赖所在窗口累计打饭时间"以及"两窗口累计打饭之和 = 前缀和"这两个结构，一维状态描述两边。

这个"贪心消序 + 背包分人"的组合在双机调度类问题里很常见：先证明局部顺序与分配无关，再把分配当成 0/1 背包做。暴力版全排列枚举也提醒我们：当两个自由度纠缠时，先证明一个自由度可以贪心固定，另一个就能用 DP 处理。

图示解析

这张 ASCII 图展示整条解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13目标：最小化最后一人吃完时刻（两台窗口，队内可自由排序）
  |
  |-- 固定窗口分配，只看单窗口
  |    max(前缀和 a + b) 最小化
  |      交换论证：b 小者在前不优 → 窗口内 b 降序最优
  |
  |-- 全体按 b 降序排序 → 子序列保持降序 → 队内顺序自由度消失
  |
  |-- 唯一决策：每人进 1 号 / 2 号窗口
  |    第 i 人总是队尾，吃完时刻只依赖该窗口累计打饭时间
  |
  `-- 0/1 背包式 DP：f[j] = 1 号窗口累计打饭 j 时的最小最晚吃完时刻
        答案 = min f[j]

从下往上看：先通过交换论证固定队内顺序（第一步的证明保证贪心安全），再让"全局排序"把两个窗口的顺序问题合二为一，最后用一维状态 $j$ 同时描述两个窗口的累计打饭时间，把指数级分法压成 $O(NV)$ 的 DP。

目录

形式化题目

思路

样例 DP 表格

代码

复杂度

总结

图示解析