P2392 kkksc03考前临时抱佛脚
题目背景
kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。
题目描述
这次期末考试，kkksc03 需要考 \(4\) 科。因此要开始刷习题集，每科都有一个习题集，分别有 \(s_1,s_2,s_3,s_4\) 道题目，完成每道题目需要一些时间，可能不等（\(A_1,A_2,\ldots,A_{s_1}\)，\(B_1,B_2,\ldots,B_{s_2}\)，\(C_1,C_2,\ldots,C_{s_3}\)，\(D_1,D_2,\ldots,D_{s_4}\)）。
kkksc03 有一个能力，他的左右两个大脑可以同时计算 \(2\) 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。
输入格式
本题包含 \(5\) 行数据：第 \(1\) 行，为四个正整数 \(s_1,s_2,s_3,s_4\)。
第 \(2\) 行，为 \(A_1,A_2,\ldots,A_{s_1}\) 共 \(s_1\) 个数，表示第一科习题集每道题目所消耗的时间。
第 \(3\) 行，为 \(B_1,B_2,\ldots,B_{s_2}\) 共 \(s_2\) 个数。
第 \(4\) 行，为 \(C_1,C_2,\ldots,C_{s_3}\) 共 \(s_3\) 个数。
第 \(5\) 行，为 \(D_1,D_2,\ldots,D_{s_4}\) 共 \(s_4\) 个数，意思均同上。
输出格式
输出一行，为复习完毕最短时间。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
\(1\leq s_1,s_2,s_3,s_4\leq 20\)。
\(1\leq A_1,A_2,\ldots,A_{s_1},B_1,B_2,\ldots,B_{s_2},C_1,C_2,\ldots,C_{s_3},D_1,D_2,\ldots,D_{s_4}\leq60\)。
Tip
b站讲解链接
这是个0/1背包问题，我Obsidian仓库总结过，我有空再整理上传到我这个static的网站吧
📌 题目分析
这道题的核心在于如何分配时间。题目要求完成 4 科复习，每科相互独立。对于每一科，kkksc03 可以同时动用左右脑，这意味着他可以将该科目的题目分成两组，分别由左脑和右脑处理。
👉 本质： 将一堆数分成两组，使得两组的和尽可能接近。这实际上是经典的 “0/1 背包问题” 或 “等和分割子集问题” 的变体。
👉 目标： 对于每一科，设其总时间为 \(Sum\)。我们希望其中一个脑负担的时间 \(now\_sum\) 尽可能接近 \(Sum/2\) 且不超过它。这样，该科目的复习时间就是 \(\max(now\_sum, Sum - now\_sum)\)，即 \(Sum - now\_sum\)。
👉 类型： 回溯算法（DFS）/ 动态规划（0/1 背包）
🧠 解题思路
1️⃣ 为什么可以使用回溯
题目明确要求使用回溯算法。由于每一科的题目数量 \(s_i\) 非常小（不超过 20），对于每道题目，我们只有两种选择：分给左脑 或者 不分给左脑（即分给右脑）。 总的状态数对于每一科来说只有 \(2^{20} \approx 10^6\)，在 4 科总计约 \(4 \times 10^6\) 次计算，这在 1 秒的时限内是完全可以接受的。
2️⃣ 递归搜索状态设计
对于每一科，我们定义一个深度优先搜索函数 dfs(index, current_sum)：
* index: 当前考虑到该科目的第几道题。
* current_sum: 当前左脑分配到的总时间。
3️⃣ 寻找最优解
在搜索过程中，我们记录一个全局变量 max_left_sum，表示在不超过 \(Sum/2\) 的前提下，左脑能达到的最大时间。
搜索结束后，该科目的最短复习时间为：\(Sum - max\_left\_sum\)。
最后将 4 科的时间累加即为答案。
💻 C++ 代码实现
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
int s[5]; // 四科题目数量
int current_subject_times[25];
int min_time_total = 0;
int max_left_sum = 0;
int current_sum_total = 0;
// index: 当前题目索引
// left_sum: 左脑当前分配的时间
void dfs(int index, int left_sum, int num_problems) {
// 边界条件：搜索完该科目所有题目
if (index > num_problems) {
// 我们希望 left_sum 尽可能接近总和的一半，但不要超过它
if (left_sum <= current_sum_total / 2) {
max_left_sum = max(max_left_sum, left_sum);
}
return;
}
// 剪枝：如果当前左脑时间已经超过总和一半，再加只会更远
if (left_sum > current_sum_total / 2) {
// 注意：这里不能直接 return，因为可能不选当前题目会更优
// 但我们可以在进入递归前判断
}
// 情况 1：这道题给左脑
dfs(index + 1, left_sum + current_subject_times[index], num_problems);
// 情况 2：这道题不给左脑（给右脑）
dfs(index + 1, left_sum, num_problems);
}
int main() {
for (int i = 1; i <= 4; i++) cin >> s[i];
for (int i = 1; i <= 4; i++) {
current_sum_total = 0;
max_left_sum = 0;
for (int j = 1; j <= s[i]; j++) {
cin >> current_subject_times[j];
current_sum_total += current_subject_times[j];
}
// 开始对这一科进行搜索
dfs(1, 0, s[i]);
// 该科最短时间 = 总时间 - 左脑能分配的最大时间（<= 1/2 总时间）
min_time_total += (current_sum_total - max_left_sum);
}
cout << min_time_total << endl;
return 0;
}
⚠️ 易错点
❌ 1. 递归层数混淆
每一科都要重新初始化 max_left_sum 和 current_sum_total。如果在切换科目时忘记重置这些变量，会导致结果错误。
❌ 2. 忽略题目“一科一科复习”的限制
题目提到“仅限于同一科”，意味着你不能左脑算数学，右脑算英语。必须等数学完全复习完（两脑空闲），才能开始下一科。因此程序逻辑应该是：计算一科的最短时间 -> 累加到总和 -> 开启下一科。
❌ 3. 搜索效率问题
虽然 \(2^{20}\) 可以通过，但在递归中可以加入一点简单的剪枝：如果 left_sum 已经远超 current_sum_total / 2，则可以停止在该分支继续累加，以提高速度。