当前位置：首页 > news >正文

每日c/c++题备战蓝桥杯(P2392 kkksc03考前临时抱佛脚)

news 2025/4/28 10:09:33

【题解】期末考试抱佛脚最短时间（动态规划 | 二进制背包）

题目链接

题目背景

kkksc03 的大学生活非常颓废，临近期末考试才开始疯狂复习。他有 4 门科目需要复习，每一科都有若干道题目，每道题目需要一定的时间完成。

幸运的是，kkksc03 有一个独特的能力：左右大脑可以同时计算两道不同的题目（但仅限于同一门科目），也就是说，同一时间可以同时做两道不同的题目。

为了能尽快开始处理洛谷上的 bug，他希望以最短的总时间完成所有复习工作。

题目描述

给定 4 门科目的题目数量和每道题目所需时间，kkksc03 必须一科一科地复习（不能同时跨科目），并且每一科允许左右脑同时处理不同的题目。

求出完成所有科目的最短总复习时间。

输入格式

第 1 行：四个正整数 s₁, s₂, s₃, s₄，分别表示第 1~4 科的题目数。
第 2-5 行：分别给出每门科目的每道题目的完成时间。

输入样例

输出格式

一行一个整数，表示复习完所有科目的最短时间。

输出样例

题目分析

这道题的核心是：

每一科单独处理，不能跨科目并行。
每一科允许左右脑同时处理两道不同的题目，等价于把题目集合分成两个子集，让两个子集的时间总量尽量平衡。

这很像背包问题！

进一步理解：

如果一个科目总时间是 sum，我们可以把所有题目划分成两部分，使得两部分的时间尽可能接近。
最慢的那部分时间，决定了完成这一科目的所需时间。
也就是：某一部分时间最长为 sum/2 的最大可达值 x，所需时间就是 max(x, sum - x)。
因为左右脑是同步进行的，所以总时间就是其中较大的那部分时间。

总结一下，每一科是独立的小问题，每一科本质上是一个0-1 背包问题，背包容量是 sum/2。

解题思路

对于每一科，读取所有题目的时间。
计算所有题目时间的总和 sum。
使用 dp[i] 表示是否可以恰好达到时间 i。
标准的 0-1 背包过程，从大到小枚举。
找到不超过 sum/2 的最大可达时间 x。
当前科目的最短时间为 max(x, sum-x)。
累加到总时间。

AC代码讲解

#include<bits/stdc++.h>
using namespace std;int main()
{int dp[1000] = { 0 };  // 背包DP数组，大小足够int time[22] = { 0 };  // 存储每科的各题时间，最多20题int s[5] = { 0 };      // 四门科目题目数量int ans = 0;           // 最后答案// 输入每科题目数量cin >> s[1] >> s[2] >> s[3] >> s[4];for (int t = 1; t <= 4; ++t)  // 处理4门科目{int sum = 0;for (int i = 1; i <= s[t]; ++i)  // 输入每道题目所需时间{cin >> time[i];sum += time[i];}// 0-1 背包求尽量接近 sum/2 的最大时间for (int j = 1; j <= s[t]; ++j){for (int i = sum / 2; i >= time[j]; --i){dp[i] = max(dp[i], dp[i - time[j]] + time[j]);}}int temp = sum - dp[sum / 2]; // temp 是两个集合时间差较大的那部分ans += max(dp[sum/2], temp);  // 加上每科最短时间// 清空dp数组，准备下一科for (int i = 1; i <= sum/2; ++i) dp[i] = 0;}cout << ans;return 0;
}

复杂度分析

单科学习部分的时间复杂度为 O(题目数 × 总时间/2)，由于
- 题目数 <= 20
- 单题时间 <= 60
- 所以总时间最多是 20 × 60 = 1200，sum/2 最多600。
因此在最坏情况下，单科DP是 O(20×600)=12000，四科一起大约 48000，运行非常快，可以轻松通过！