kkksc03 考前临时抱佛脚

题意

有 4 科题目，每科必须单独完成。做同一科时，左右脑可以同时做两道题，相当于把这一科的题目分给两个处理器，耗时是两边总时间的较大值。

求 4 科总耗时最小值。

思路

每科互不影响，可以分别求最优耗时后相加。

对一科题目，问题变成：把若干时间分成两组，使两组总和尽量接近。设总和为 total，如果一组时间为 left，另一组就是 total-left，这一科耗时：

text

1max(left, total - left)

用集合 reachable 表示“当前能凑出的左脑时间”。初始只有 {0}。每加入一道题 time，新的可达时间包括：

text

1
2原来的 current
current + time

小 DP 表

例如某科时间为 [4, 3]：

已处理题目	reachable
无	`{0}`
加入 4	`{0, 4}`
加入 3	`{0, 3, 4, 7}`

总和为 7，选择 left=3 或 4，耗时都是 4。

Python 知识

set 很适合保存“能凑出的所有时间”。
reachable |= {current + time for current in reachable} 表示把新可达状态合并回集合。
每科写成函数 subject_time(times)，主流程只负责读入和累加。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21def subject_time(times):
    total = sum(times)
    reachable = {0}

    for time in times:
        reachable |= {current + time for current in reachable}

    best = total
    for left in reachable:
        best = min(best, max(left, total - left))
    return best


sizes = list(map(int, input().split()))
answer = 0

for size in sizes:
    times = list(map(int, input().split()))
    answer += subject_time(times[:size])

print(answer)

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/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int s[4];
int t[4][25];
int dp[1500]; // dp[i] = 1 表示能凑出时间 i

int subject_time(int times[], int len) {
    int total = 0;
    for (int i = 0; i < len; i++) total += times[i];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < len; i++)
        for (int j = total; j >= times[i]; j--)
            if (dp[j - times[i]]) dp[j] = 1;
    int best = total;
    for (int left = 0; left <= total; left++)
        if (dp[left]) best = min(best, max(left, total - left));
    return best;
}

int main() {
    for (int i = 0; i < 4; i++) cin >> s[i];
    for (int i = 0; i < 4; i++)
        for (int j = 0; 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 << endl;
    return 0;
}

复杂度

每科总时间最多 20 * 60 = 1200，集合状态数不超过总时间加一。时间复杂度约为 $O(4 \cdot s \cdot sum)$ ，空间复杂度为 $O(sum)$ 。

总结

“左右脑同时做”本质是把任务划分成两组，使较大的一组尽量小，也就是接近一半的子集和问题。

kkksc03 考前临时抱佛脚

目录

题意

思路

小 DP 表

Python 知识

代码

复杂度

总结