每日c/c++题 备战蓝桥杯(P2392 kkksc03考前临时抱佛脚)
【题解】期末考试抱佛脚最短时间(动态规划 | 二进制背包)
题目链接
题目背景
kkksc03 的大学生活非常颓废,临近期末考试才开始疯狂复习。他有 4 门科目需要复习,每一科都有若干道题目,每道题目需要一定的时间完成。
幸运的是,kkksc03 有一个独特的能力:左右大脑可以同时计算两道不同的题目(但仅限于同一门科目),也就是说,同一时间可以同时做两道不同的题目。
为了能尽快开始处理洛谷上的 bug,他希望以最短的总时间完成所有复习工作。
题目描述
给定 4 门科目的题目数量和每道题目所需时间,kkksc03 必须一科一科地复习(不能同时跨科目),并且每一科允许左右脑同时处理不同的题目。
求出完成所有科目的最短总复习时间。
输入格式
- 第 1 行:四个正整数 s₁, s₂, s₃, s₄,分别表示第 1~4 科的题目数。
- 第 2-5 行:分别给出每门科目的每道题目的完成时间。
输入样例
1 2 1 3
5
4 3
6
2 4 3
输出格式
一行一个整数,表示复习完所有科目的最短时间。
输出样例
20
题目分析
这道题的核心是:
- 每一科单独处理,不能跨科目并行。
- 每一科允许左右脑同时处理两道不同的题目,等价于把题目集合分成两个子集,让两个子集的时间总量尽量平衡。
这很像背包问题!
进一步理解:
- 如果一个科目总时间是
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,运行非常快,可以轻松通过!
总结
- 本题本质是每科单独的背包问题。
- 充分理解左右脑同步处理的能力,将问题转化为集合划分问题。
- 小数据量背包,暴力DP即可!
如果你掌握了这一类背包技巧,很多像 “集合划分”、“最大平均值”、“划分集合使得子集和最接近” 等问题都可以迎刃而解!
如果你想要,我还可以帮你附一版更简洁版代码!要不要?✨
相关文章:
每日c/c++题 备战蓝桥杯(P2392 kkksc03考前临时抱佛脚)
【题解】期末考试抱佛脚最短时间(动态规划 | 二进制背包) 题目链接 题目背景 kkksc03 的大学生活非常颓废,临近期末考试才开始疯狂复习。他有 4 门科目需要复习,每一科都有若干道题目,每道题目需要一定的时间完成。…...
徽客松S1 | 合肥首场 AI 黑客松招募
越来越多的黑客松在各个城市出现!5 月 10 日,合肥,12 小时极速挑战。 我们和本次「徽客松」发起人 SDL 也是在一个黑客松上相识。当你的城市还没有黑客松可参加,与其等待,不如学习 SDL,自己发起一个&#…...
单片机-89C51部分:6、按键
飞书文档https://x509p6c8to.feishu.cn/wiki/EtkHw8MG0ipz3NkHlZEcwpEnn4g 一、应用场景: 轻触开关、按键、电容开关、光栅传感器、微动、关电开关 二、原理: 轻触按键可以理解为两根导线,按下时导线连接,松开时导线断开。我们可…...
小结: DHCP
交换机的物理接口分批地址池、全局分配地址池 分批地址池(接口地址池/局部分配) 按物理接口(如 VLAN 接口、SVI、物理端口)划分,每个接口单独配置一个小型地址池。适合规模较小、子网划分清晰的场景。配置方法示例&…...
matlab simulink中理想变压激磁电流容易有直流偏置的原因分析。
simulink把线性变压器模块拉出来,设置没有绕线电阻的变压器,激磁电感和Rm都有,然后给一个50%占空比的方波,幅值正负10V,线路中设置一个电阻,模拟导线阻抗。通过示波器观察激磁电流,发现电阻越小…...
国产三维CAD皇冠CAD在「通用设备制造业」建模教程:台式起重机
在制造业数字化转型的浪潮中,三维CAD软件已成为装备设计的核心工具,而国产软件的崛起正悄然改变行业格局。皇冠CAD(CrownCAD)作为中国自主研发的云端三维CAD平台,凭借全栈可控的底层架构、高效协同的设计流程及复杂场景…...
Day 12
文件操作 文件文件操作文件函数课堂笔记 文件 1)概述 FILE 所有平台的名字都一样,FILE 是一个结构体类型,里面的成员功能一样,不同平台成员的名字不一样。 FILE *fp 1、fp指针,只用调用了fopen().在堆区分配空间,把地址返回给fp 2、fp指针…...
Lua 第11部分 小插曲:出现频率最高的单词
在本章中,我们要开发一个读取并输出一段文本中出现频率最高的单词的程序。像之前的小插曲一样,本章的程序也十分简单但是也使用了诸如迭代器和匿名函数这样的高级特性。 该程序的主要数据结构是一个记录文本中出现的每一个单词及其出现次数之间关系的表。…...
自然语言处理之机器翻译:注意力机制在低资源翻译中的突破与哲思
## 被忽视的7000种语言 在人工智能翻译技术突飞猛进的今天,一个残酷的事实被刻意掩盖:全球7000种语言中,超过95%缺乏构建现代机器翻译系统所需的基础资源。当我们在庆贺Transformer模型将英德翻译BLEU值推高至40%时,那些承载着人类文明基因的少数民族语言,正在经历着前所未…...
SQL 处理重复数据之技巧(Techniques for Handling Duplicate Data with SQL)
SQL 处理重复数据之技巧 ❝ 在日常数据库操作中,我们经常会遇到重复数据的问题。重复数据不仅会占用存储空间,还可能导致数据分析结果不准确。本文将详细讲解 SQL 中处理重复数据的常用方法,帮助你更高效地管理数据库中的数据。 一、为什么会…...
Redis01-基础-入门
零、文章目录 Redis01-基础-入门 1、认识 NoSQL NoSQL 知识请参考:https://blog.csdn.net/liyou123456789/article/details/132612444 2、认识 Redis (1)简介 Redis(Remote Dictionary Server,远程字典服务&…...
辞九门回忆
2025年月日,13~30℃,挺好的 待办: 《高等数学2》期末试卷 高数重修电子版材料 冶金《物理》期末试卷 《物理[2]》期末试卷 批阅冶金《物理》作业→→统计平时成绩 遇见:遇见一位小姐姐。 感受或反思:不主动推动关系&a…...
全球城市范围30米分辨率土地覆盖数据(1985-2020)
Global urban area 30 meter resolution land cover data (1985-2020) 时间分辨率年空间分辨率10m - 100m共享方式保护期 277 天 5 时 42 分 9 秒数据大小:8.98 GB数据时间范围:1985-2020元数据更新时间2024-01-11 数据集摘要 1985~2020全球城市土地覆…...
java编程式、声明式事务简单介绍
大家吼鸭!今天学习新项目的时候,项目中运用了编程式项目,有点不理解什么叫编程式事务,于是我去查询了一些资料,大概了解了一下。现在做一个简单的介绍。 编程式事务和声明式事务的区别 现在想象一个场景,…...
Golang 遇见 Kubernetes:云原生开发的完美结合
Golang 和 Kubernetes 简介 Golang 概述 Golang,也称为 Go,是由 Google 开发的一种开源编程语言。Go 由 Robert Griesemer、Rob Pike 和 Ken Thompson 设计,于 2009 年首次发布,此后在各个领域都获得了广泛的关注,尤其…...
第三章,GRE和MGRE
VPN---虚拟专用网络 VPN的核心技术----隧道技术---封装 GRE---通用路由封装 配置 GRE的配置: R1: [r1]interface Tunnel 0/0/0 ---创建一个虚拟的隧道接口 [r1-Tunnel0/0/0]ip address 192.168.3.1 24 ---给隧道接口分配一个IP地址 [r1-Tunnel0/0/0]t…...
redis常用集合操作命令
在 Redis 的命令行界面(redis-cli)中, Redis 的集合(Set)是无序的,且集合中的元素是唯一的。Redis 本身没有直接提供获取集合中某个特定属性的命令,因为集合中的元素是简单的值,而不…...
vue3中ref在js中为什么需要.value才能获取/修改值?
文章目录 [TOC](文章目录) 一、ref定义值什么情况下需要.value1. 情况1:在js中需要使用.value2. 情况2:在html模版中不需要使用.value3. 情况31.代码2.效果3. 二、重新了解一下vue2和vue3的响应式1.vue2(Object.defineProperty)2.vue3(proxy&…...
使用vue2 开发一个纯静态的校园二手交易平台-前端项目练习
这篇文章给大家分享一个适合练习学习前端技术的项目:校园二手交易平台系统。 因为最近在学习vue相关的技术,所以就根据学习的前端技术,来写一些纯前端的项目来练习,这篇文章主要是分享一下 我做的这个项目的一些功能,如…...
使用wavesurferJs实现录音音波效果
效果图展示 插件安装 npm i wavesurfer实现过程 <!-- author: weileiming date: 2025-04-26 14:04:08 description: 悬浮音波层 props:isRecord: 录制状态waveOptions: 音波基础配置overlayStyle: 基础蒙层配置 methods:togglePlay: 切换录制状态 --> <template>…...
Golang 类型方法
在 Go 语言中,方法绑定到任意类型的特性可以称为 “类型方法(Type Methods)” 或 “接收者方法(Receiver Methods)”,它体现了以下几种核心编程思想: 1. 官方术语:接收者方法&#x…...
多模态常见面试题
多模态常见面试 一、最近关注的论文,多模态视觉大模型(CLIP,DALLE)?二、blip2的架构,优势和之前多模态模型的区别?三、多模态融合后,怎样知道最终结果受哪种模态影响更大?四、多模态中常见的SOTA模型有哪些…...
LangChain构建大模型应用之RAG
RAG(Retrieval-augmented Generation 检索增强生成)是一种结合信息检索与生成模型的技术,通过动态整合外部知识库提升大模型输出的准确性和时效性。其核心思想是在生成答案前,先检索外部知识库中的相关信息作为上下文依据…...
Git 全面解析:从核心概念到生态应用
Git 一、Git 起源与定位 诞生背景:2005 年由 Linus Torvalds 为管理 Linux 内核开发而设计,因 BitKeeper 许可证争议,急需分布式版本控制系统(DVCS)替代集中式工具(如 SVN)。核心优势&#x…...
国产免费工作流引擎star 5.9k,Warm-Flow版本升级1.7.0(新增大量好用功能)
国产免费工作流引擎star 5.9k,Warm-Flow版本升级1.7.0(新增大量好用功能) 主要更新内容项目介绍功能思维导图设计器流程图演示地址官网Warm-Flow视频 之前大家一直吐槽没有撤销、驳回到上一个任务和拿回等功能,此次版本全都带给大…...
camera知识学习
1、DSP DSP(数字信号处理器),这个是介于sensor和ISP处理的一个处理阶段,会进行一些传感器方面的偏硬件处理,再进行数据格式的转换,将raw数据转换成RGB数据或者YUV数据...
Java高频常用工具包汇总
Java高频常用工具包汇总 Java生态系统中有许多广泛使用的工具包,以下是一些高频常用的工具包分类汇总: 1. 核心工具包 Apache Commons系列 Commons Lang - 提供各种基础工具类Commons IO - 文件/IO操作工具Commons Collections - 集合扩展工具Commons …...
蓝桥杯 16. 密文搜索
密文搜索 原题目链接 题目描述 福尔摩斯从 X 星收到一份资料,全部是小写字母组成。 他的助手提供了另一份资料:许多长度为 8 的密码列表。 福尔摩斯发现,这些密码是被打乱后隐藏在先前那份资料中的。 请你编写一个程序,从第…...
Spring Boot 中多线程的基础使用
1. 核心机制 Spring Boot 通过 TaskExecutor 和 Async 注解支持多线程编程,结合线程池管理,有效提升应用性能。核心组件包括: EnableAsync:启用异步任务支持。 Async:标记方法为异步执行。 ThreadPoolTaskExecutor&…...
660SJBH企业信息管理系统
第一章 问题来源 1.1 课题提出背景和意义 由于企业规模进一步扩大,企业信息的管理也变得越来越复杂。为此,切实有效的把企业信息管理系统引入企业管理领域中,对于促进企业管理制度和提高企业质量有着显着意义。 Internet的发展使我们的企业…...
OpenCV实验室工具的使用
OpenCV实验室工具是一个调用OpenCV常见函数,让用户调整参数,快速得到试验结果的工具软件。 软件界面中包含三列,第一列是功能菜单,第二列是实现某一功能时需要输入的参数,第三列是图像处理历史。 OpenCV实验室包含了常…...
月之暗面开源-音频理解、生成和对话生成模型:Kimi-Audio-7B-Instruct
一、Kimi - Audio 简介 Kimi - Audio 是一个开源的音频基础模型,在音频理解、生成和对话等方面表现出色。其设计旨在作为一个通用的音频基础模型,能够在单一统一的框架内处理各种音频处理任务,如语音识别(ASR)、音频问…...
依赖于切片级标签,结合信息瓶颈理论,对弱监督病理切片分类模型进行微调
小罗碎碎念 在医学AI领域,病理全切片图像(WSI)分析意义重大,但面临诸多难题。 高分辨率的WSI使得获取精确注释极为困难,且计算成本高昂。 多实例学习(MIL)虽能利用WSI级弱监督缓解注释压力&…...
UE5 NDisplay 单主机打包运行
前言 最近在做UE的左右眼双屏输出,找了半天只有近年来比较火的NDispaly可以做这件事了,看了一下官方的教程写的很全面,但是相对笼统了一些,发现B站和一些博客了也写了有,但是我建议还是好好过一遍官方文档吧࿰…...
Kubernetes/KubeSphere 安装踩坑记:从 context deadline exceeded 到成功部署的完整排障笔记
目录 Kubernetes/KubeSphere 安装踩坑记:从 context deadline exceeded 到成功部署的完整排障笔记 一、问题现象 二、第一手日志采集 三、定位思路 四、分步解决 4-1 处理 pause:3.8 4-2 处理 kube-apiserver:v1.31.0 五、再次安装并验证 六、经验总结 七…...
SpringMVC 静态资源处理 mvc:default-servlet-handler
我们先来看看效果,当我把这一行注释掉的时候: 我们来看看页面: 现在我把注释去掉: 、 可以看到的是,这个时候又可以访问了 那么我们就可以想,这个 <mvc:default-servlet-handler />它控制着我们页面的访问…...
2、Linux操作系统下,ubuntu22.04版本安装搜狗输入法
1.添加中文语言支持,打开此窗口的步骤如下: system setting>language and region>language>install/remove language,之后弹出下面的窗口,点击“reminder me later勾选Chinese(simplified)&#…...
go语言八股文(四)
1.go语言中defer的变量快照在什么情况下会生效 1. 变量在 defer 被注册时的值被捕获 当 defer 被注册时,它会捕获变量在那一刻的值。如果变量是值类型(如基本类型、结构体等),defer 会捕获该值的副本;如果变量是指针类…...
烽火HG680-MC_晨星MSO9385芯片-2+8G_安卓9.0_不分地区通刷卡刷固件包
烽火HG680-MC_晨星MSO9385芯片-28G_安卓9.0_不分地区通刷卡刷固件包 刷机教程: 1、准备一个优盘卡刷强刷刷机,用一个usb2.0的8G以下U盘,fat32,2048块单分区格式化(强刷对U盘非常非常挑剔,usb2.…...
秒杀压测计划 + Kafka 分区设计参考
文章目录 前言🚀 秒杀压测计划(TPS预估 测试流程)1. 目标设定2. 压测工具推荐3. 压测命令示例(ab版)4. 测试关注指标 📦 Kafka Topic 分区设计参考表1. 单 Topic 设计2. 分区路由规则设计(Part…...
跨境电商货物体积与泡重计算器:高效便捷的物流计算工具
跨境电商货物体积与泡重计算器:高效便捷的物流计算工具 工具简介 货物体积与泡重计算器是一款免费的在线工具,专门为物流从业者、跨境电商卖家和需要计算货物运输体积重量的用户设计。这款工具可以帮助您快速计算货物的体积和对应的空运、快递泡重&…...
隧道代理ip的优势
日益复杂的互联网环境中,爬虫技术已经成为大数据不可或缺的一环。提到代理IP,大部分人首先想到的是普通的静态IP或动态代理IP,然而,隧道代理IP――这一更为高效、灵活的选择,在许多场景中能为开发者们提供绝佳的技术支…...
Selenium自动化测试+OCR-获取图片页面小说
🍅 点击文末小卡片,免费获取软件测试全套资料,资料在手,涨薪更快 随着爬虫技术的发展,反爬虫技术也越来越高。 目前有些网站通过自定义字体库的方式实现反爬,主要表现在页面数据显示正常,但是…...
MySQL 锁等待超时问题解析:Lock wait timeout exceeded;try restarting transaction
目录 一、问题背景二、问题原因三、解决方案1. 重启事务2. 优化事务管理3. 调整锁等待超时设置4. 分析并优化锁竞争5. 查找并终止持有锁的操作6. 优化 SQL 语句四、预防措施五、总结在使用 MySQL 数据库时, Lock wait timeout exceeded;try restarting transaction 这个错误…...
学习笔记2(Lombok+算法)
Lombok : 介绍: Lombok 是一个在 Java 开发中广泛使用的开源库,它的主要作用是通过注解的方式,减少 Java 代码中大量的样板代码(如 getter、setter、构造函数等),从而让代码更加简洁、易读和易…...
【音视频】SDL简介
官网:官网 文档:文档 SDL(Simple DirectMedia Layer)是一套开放源代码的跨平台多媒体开发库,使用C语言写成。SDL提供数种控制图像、声音、输出入的函数,让开发者只 要用相同或是相似的代码就可以开发出跨多…...
信创系统资产清单采集脚本:主机名+IP+MAC 一键生成 CSV
原文链接:信创系统资产清单采集脚本:主机名IPMAC 一键生成 CSV Hello,大家好啊!今天给大家带来一篇在信创终端操作系统上自动批量采集主机名、IP 和 MAC 并导出为 CSV 表格的实战文章!本方案使用 sshpass 和 Bash 脚本…...
Python爬虫(8)Python数据存储实战:JSON文件读写与复杂结构化数据处理指南
目录 一、背景与核心价值二、JSON基础与核心应用场景2.1 JSON数据结构规则2.2 典型应用场景 三、Python json模块核心操作3.1 基础读写:dump()与load()3.2 字符串与对象的转换:dumps()与loads() 四、处理复杂数据类型4.1 日期时间对象…...
OpenStack私有云详细介绍
引言 企业部署云计算服务的模式有公有云、私有云、混合云三大类。 公有云是云计算服务提供商为公众提供服务的云计算平台,理论上任何人都可以通过授权接入该平台。 私有云是云计算服务提供商为企业在其内部建设的专有云计算系统,私有云系统存在于企业防火…...
6.图的OJ题(1-10,未完)
310. 最小高度树 - 力扣(LeetCode) 分析:n个顶点的无环无向连通图,有n-1条边。 1)任意两点有且只有一条路径 2)路径最远的两顶点必为叶子节点 且根据证明可以得出以下两个性质: 1.最小高度树的根…...