kkksc03 考前临时抱佛脚

形式化题目

有 4 组物品（对应 4 科），第 $i$ 组有 $s_i$ 件物品，每件物品有一个耗时。每组物品必须连续处理，处理一组时有两个处理器（左脑、右脑）可以同时各处理一件物品；把一组物品划分成两组后，这组物品的处理时间等于两组耗时和的较大值。

要求：求 4 组物品处理时间的最小总和。

等价地，每组物品要划分成两个集合，使两个集合和的最大值最小——即找到一个子集和，使其尽量接近总和的一半。

思路

先看一个可以直接验证想法的朴素解：

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/**
 * 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-13 13:20
 * update_at: 2026-08-13 13:20
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举所有分法，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int s[4];        // s[i] 表示第 i 科的题目数量
int t[4][MAXN];  // t[i][j] 表示第 i 科第 j 道题的耗时
int n;           // 当前正在枚举的科的题目数量
int times[MAXN]; // 当前科的每道题耗时（从 t 拷贝过来）
int choose[MAXN]; // choose[i] = 0/1 表示第 i 题分给右脑 / 左脑
int best;        // 当前科的最优耗时

// 一条完整 01 序列已经生成，按选择统计两组时间并更新最优值。
void calc_answer() {
    int left_sum = 0, right_sum = 0;
    for (int i = 1; i <= n; i++) {
        if (choose[i] == 1)
            left_sum += times[i];
        else
            right_sum += times[i];
    }
    int cost = max(left_sum, right_sum); // 这一科耗时 = 两边时间的较大值
    if (cost < best) best = cost;
}

// 枚举第 dep 道题的归属：0 给右脑，1 给左脑。
void dfs(int dep) {
    if (dep == n + 1) { // 一条完整的 01 序列已生成
        calc_answer();
        return;
    }
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

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

    for (int i = 0; i < 4; i++) cin >> s[i];
    for (int i = 0; i < 4; i++)
        for (int j = 1; j <= s[i]; j++) cin >> t[i][j];

    int ans = 0;
    for (int i = 0; i < 4; i++) {
        n = s[i];
        for (int j = 1; j <= n; j++) times[j] = t[i][j];
        best = 0x7fffffff;
        dfs(1); // 枚举 2^n 种分法，只适合小数据
        ans += best;
    }
    cout << ans << '\n';
    return 0;
}

这个暴力把每科的分法看成一串 01 选择：choose[i] = 0/1 表示第 i 道题给右脑还是左脑。递归先生成完整的 choose[]，到叶子节点再按选择统计左右两组的时间，并更新该科的最优耗时。 $2^n$ 条 01 序列正好对应全部 $2^n$ 种分法，但它只适合小数据： $n = 20$ 时单科就约 $10^6$ 种分法。

关键观察是：单科耗时只由"左脑组凑出的时间 left"决定，即 $\max(left, total - left)$ ，至于具体是哪几道题凑出来的并不重要；而且 left 可达当且仅当互补的 total - left 可达。因此问题压缩成：用 0/1 背包一维子集和 DP 找出不超过 total/2 的最大可达时间 left，该科耗时就是 total - left。这个转移正是 rbook《01 背包》模板（knapsack-01-1d）的可达性变体。

以样例第二科 [4, 3]（总和 7）为例，看 DP 表如何变化：

已处理题目	0	3	4	7
无	1	0	0	0
加入 4	1	0	1	0
加入 3	1	1	1	1

行表示已经考虑了哪些题目，列表示左脑时间 j，单元格为 1 表示该时间可达。观察"加入 3"这一行：可达集合变成 $\{0, 3, 4, 7\}$ ，其中 3 来自"选 3 不选 4"，4 保留自上一行（不选 3），7 来自两个都选。总和 total = 7，从 total/2 = 3 向下扫描找到最大可达 left = 3，该科耗时 7 - 3 = 4。

代码

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/**
 * 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-13 13:20
 * update_at: 2026-08-13 13:20
 */
// main.cpp：每科独立求最优耗时，用 0/1 背包一维子集和 DP，
// 找不超过总时间一半的最大可达左脑时间，答案取另一边的总时间。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;     // 每科最多 20 道题
const int MAXSUM = 1500; // 每科总时间上限 20 * 60 = 1200

int s[4];          // s[i] 表示第 i 科的题目数量
int t[4][MAXN];    // t[i][j] 表示第 i 科第 j 道题的耗时
int dp[MAXSUM];    // dp[j] = 1 表示用当前科的题目能凑出左脑时间 j

// 求一科的最短耗时：把题目分给左右两组，使两组总时间的较大值最小。
int subject_time(int times[], int len) {
    int total = 0;
    for (int i = 1; i <= len; i++) total += times[i];

    // 0/1 背包一维子集和：dp[j] 由 dp[j - times[i]] 转移而来
    memset(dp, 0, sizeof(dp));
    dp[0] = 1; // 一道题都不给左脑
    for (int i = 1; i <= len; i++)
        // 逆序枚举，保证每道题只用一次（0/1 背包的写法）
        for (int j = total; j >= times[i]; j--)
            if (dp[j - times[i]]) dp[j] = 1;

    // 找不超过 total/2 的最大可达 left，
    // 此时另一组时间是 total - left，这一科耗时就是它。
    int left = total / 2;
    while (dp[left] == 0) left--;
    return total - left;
}

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

    for (int i = 0; i < 4; i++) cin >> s[i];
    for (int i = 0; i < 4; i++)
        for (int j = 1; j <= s[i]; j++) cin >> t[i][j];

    int ans = 0;
    for (int i = 0; i < 4; i++) ans += subject_time(t[i], s[i]);
    cout << ans << '\n';
    return 0;
}

复杂度

时间：单科 $O(s_i \cdot total_i)$ ，其中 $total_i \leqslant 1200$ ；4 科合计 $O(4 \cdot s \cdot total)$ ，约 $10^5$ 次操作。
空间： $O(total)$ 的 dp 数组加题目耗时表，约 1500 个整数。

总结

“左右脑同时做同一科的两道题"本质是一个双处理器调度问题：把题目划分成两组，使较大的一组总时间尽量小，也就是让某组的子集和最接近总和的一半。每科独立、答案相加；单科用 0/1 背包一维子集和 DP 在 $O(s \cdot total)$ 内解决，配合"互补子集"性质，从 total/2 向下找第一个可达时间即可。枚举 $\to$ 状态压缩这条主线在这道题上非常清晰：暴力枚举每道题的归属，而 DP 只保留"可达的时间”。

图示解析

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22每科独立
  单科耗时 = 左右两组题目耗时和的较大值，4 科答案相加
        |
        v
01 序列暴力（brute.cpp）
  每条 01 序列表示一道题给左脑还是右脑
  枚举全部 2^n 种分法，叶子处算 max(left, right)
        |
        | 瓶颈：2^n 种分法，n = 20 时单科约 10^6 种，大量分法共享同一个 left
        v
关键观察
  单科耗时只由左脑时间 left 决定：max(left, total - left)
  left 可达 ⟺ total - left 可达（互补），最优分法必有一边 <= total/2
        |
        v
0/1 背包子集和 DP（main.cpp）
  dp[j] = 1 表示左脑时间 j 可达
  每道题逆序更新 dp[j] = dp[j] | dp[j - times[i]]（保证每题只用一次）
  从 total/2 向下找第一个可达的 left，答案 = total - left
        |
        v
复杂度 O(4 · s · total)，total <= 1200，空间 O(total)

图中三条主线分别对应"暴力在哪里慢"“观察到什么性质”“正式解如何利用这个性质”。核心一步是把状态从"每道题的归属"压缩成"可达的时间"，互补性质则保证了在 total/2 以下找最大值不会漏掉最优解。