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

【蓝桥】线性DP--最快洗车时间

题目描述​

解题思路

完整代码

举例

总结

基于 0/1 背包思想 解决 洗车时间分配问题,本质上是子集和问题【给定一个 正整数数组 nums 和一个目标值 target,判断是否可以从 nums 选择 若干个数(每个数最多选一次),使其和 恰好等于 target

题目描述

 

解题思路

一开始用的使用了排序+贪心的方法:

  • 对洗车时间从大到小排序(先分配长时间的任务)。
  • 优先分配给当前时间较短的那个人(类似负载均衡)。
  • 遍历数组,依次分配,最终返回 max(wash1, wash2)

        但这种思路是错的,求的是局部最优解 ,局部最优不一定导致全局最优,即在每一步都选择当前看起来最好的方案,并不一定能得到最优解

正确方法:设所有洗车时间之和为 total,我们希望 找到一个子集,使得其和 best 尽可能接近 total / 2。这样 max(best, total - best) 就是两人最优的洗车时间

1. 定义状态

dp[j] 表示是否可以从数组 nums 中选取若干个数,使得它们的和为 j

  • dp[j] = true 表示存在一个子集的和恰好等于 j
  • dp[j] = false 表示无法找到这样的子集。

2. 状态转移方程

对于当前遍历的 nums[i]

  • 如果不选 nums[i],那么 dp[j] 由前一轮 dp[j] 继承;
  • 如果选 nums[i],那么 dp[j] 取决于 dp[j - nums[i]] 是否为 true,即如果 j - nums[i] 之前是可行的,那么 j 也是可行的。

状态转移方程:

3. 初始化

  • dp[0] = true(因为总和为 0 的子集是空集,肯定可以达到)。
  • 其他 dp[j] 初始设为 false

4. 遍历顺序

  • 外层循环 遍历 nums[i](每个数只能选一次,必须按顺序遍历)。
  • 内层循环 采用 逆序 for (int j = target; j >= nums[i]; j--),确保 nums[i] 只被选取 一次
  • 最终遍历最终的DP数组,从 target 开始向 0 逆序查找 最大的 i,满足 dp[i] == true

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110; // 设定数组大小
bool dp[N];  // 0/1 背包 DP 数组
int car[N];  // 存储每辆车的洗车时间
int n, target, total; // 变量定义int main() {cin >> n; // 读取车辆数量for (int i = 1; i <= n; i++) {cin >> car[i];total += car[i]; // 计算洗车时间总和}target = total / 2; // 目标是尽量分成两半dp[0] = true; // 初始状态,和为 0 一定是可行的for (int i = 1; i <= n; i++) { // 遍历每辆车for (int j = target; j >= car[i]; j--) { // 逆序遍历dp[j] = dp[j] || dp[j - car[i]];}}int best = 0;// 找到最接近 total/2 的可行解for (int i = target; i >= 0; i--) { if (dp[i]) {best = i;break;}}cout << max(best, total - best); // 计算最短最大时间return 0;
}

举例

n = 4
car = [8, 6, 5, 5]
total = 8 + 6 + 5 + 5 = 24
target = total / 2 = 24 / 2 = 12

初始化dp

dp = [true, false, false, ..., false]  // 长度为 target + 1,即 13

第 1 辆车 (洗车时间 8): 

dp[12] = dp[12] || dp[12 - 8] = false || dp[4] = false
dp[11] = dp[11] || dp[11 - 8] = false || dp[3] = false
dp[10] = dp[10] || dp[10 - 8] = false || dp[2] = false
dp[9] = dp[9] || dp[9 - 8] = false || dp[1] = false
dp[8] = dp[8] || dp[8 - 8] = false || dp[0] = true   // dp[8] = true

第 2 辆车 (洗车时间 6): 

dp[12] = dp[12] || dp[12 - 6] = false || dp[6] = false
dp[11] = dp[11] || dp[11 - 6] = false || dp[5] = false
dp[10] = dp[10] || dp[10 - 6] = false || dp[4] = false
dp[9] = dp[9] || dp[9 - 6] = false || dp[3] = false
dp[8] = dp[8] || dp[8 - 6] = true  || dp[2] = false
dp[7] = dp[7] || dp[7 - 6] = false || dp[1] = false
dp[6] = dp[6] || dp[6 - 6] = false || dp[0] = true   // dp[6] = true

.......

最终

dp = [true, false, false, false, false, true, true, false, true, true, true, true, false]

总结

转换成 0/1 背包问题,利用 动态规划 解决。
dp[j] 表示是否能凑出 j 这个和,递推转移 dp[j] = dp[j] || dp[j - car[i]]
时间复杂度 O(n * sum/2),适用于 sum ≤ 10^4
贪心方法可能失效,而动态规划保证最优解

相关文章:

【蓝桥】线性DP--最快洗车时间

题目描述​ 解题思路 完整代码 举例 总结 基于 0/1 背包思想 解决 洗车时间分配问题&#xff0c;本质上是子集和问题【给定一个 正整数数组 nums 和一个目标值 target&#xff0c;判断是否可以从 nums 选择 若干个数&#xff08;每个数最多选一次&#xff09;&#xff0c;使…...

Spring Boot比Spring多哪些注解?

Spring Boot 相比 Spring 多了很多自动化配置和简化开发的注解&#xff0c;主要包括以下几类&#xff1a; Spring Boot 启动与自动配置相关Spring Boot 配置相关Spring Boot Web 相关Spring Boot 测试相关Spring Boot 条件装配相关Spring Boot 监控与 Actuator 相关 1. Spring…...

springboot021校园周边美食探索及分享平台

版权声明 所有作品均为本人原创&#xff0c;提供参考学习使用&#xff0c;如需要源码数据库配套文档请移步 www.taobysj.com 搜索获取 技术实现 开发语言&#xff1a;Javavue。 框架&#xff1a;后端spingboot前端vue。 模式&#xff1a;B/S。 数据库&#xff1a;mysql。 开…...

【网络通信】传输层之UDP协议

【网络通信】传输层之UDP协议 传输层端对端通信实现端到端通信的关键技术 UDP协议再谈端口号端口号划分关于端口号的两个问题 UDP协议基本格式UDP通信的特点UDP的缓冲区UDP数据报的最大长度基于UDP的应用层协议如何封装UDP报文以及如何交付UDP报文进一步理解封装和解包 传输层 …...

Python环境搭建与量化交易开发:从基础到实战

Python环境搭建与量化交易开发&#xff1a;从基础到实战 在量化交易领域&#xff0c;Python因其强大的数据处理能力和丰富的库支持而成为首选编程语言。本文将指导您如何在本地搭建一个适合量化交易的Python环境&#xff0c;并介绍一些实用的工具和技巧。 《QMT开通规则分享》…...

软著申请(六)软著返修流程【2025年最新版】

软著申请(六)软著返修流程【2025年最新版】 一、软著返修流程1、软著返修流程须知2、相关细节二、针对大模型特殊补正条件三、备注本服务提供详细的软件著作权申请流程指导。申请人严格按照指导步骤完成申请,若最终未能成功获得著作权登记,可联系服务提供方进行免费咨询和指…...

SOUI基于Zint生成Code11码

Code 11 是一种高密度的数字条形码&#xff0c;主要用于标识电信设备和电子元件。它的名称来源于其能够编码 11 种字符&#xff1a;数字 0-9 和连接符 -。Code 11 是一种双向可读的条形码&#xff0c;支持校验位以提高数据准确性。 在使用BARCODE_CODE11码制生成code 11码时可指…...

sqlilabs第八关

?id1 and sleep(2)-- 发现页面存在注点&#xff0c;使用时间盲注脚本进行注入--- import requestsdef inject_database(url):name #name用于存储猜测出的数据库名称 for i in range(1, 20): # 假设数据库名称长度不超过20low 48 # 0high 122 # zmiddle (low high…...

基于HAL库的按钮实验

实验目的 掌握STM32 HAL库的GPIO输入配置方法。 实现通过按钮控制LED亮灭&#xff08;支持轮询和中断两种模式&#xff09;。 熟悉STM32CubeMX的外部中断&#xff08;EXTI&#xff09;配置流程。 实验硬件 开发板&#xff1a;STM32系列开发板&#xff08;如STM32F103C8T6、N…...

DeepSeek 突然来袭,AI 大模型变革的危机与转机藏在哪?

随着人工智能技术的飞速发展&#xff0c;大模型领域不断涌现出具有创新性的成果。DeepSeek 的横空出世&#xff0c;为 AI 大模型领域带来了新的变革浪潮。本文将深入探讨 DeepSeek 出现后 AI 大模型面临的危机与转机。 冲冲冲&#xff01;&#xff01;&#xff01; 目录 一、…...

prompt技术结合大模型 生成测试用例

要利用prompt技术结合大模型对目标B/S架构软件系统进行测试,以下以使用Python调用OpenAI的GPT模型进行功能测试用例生成,再借助Selenium库执行测试为例,给出一个完整的实现示例。 前提条件 安装依赖库:你需要安装openai和selenium库,可以使用以下命令进行安装:pip insta…...

【C++ 真题】P2920 [USACO08NOV] Time Management S

P2920 [USACO08NOV] Time Management S 题目描述 Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1…N (1 < N < 1,000) to accomplish (like milking the cows, cleaning the …...

pip安装指定版本的包

个人博客地址&#xff1a;pip安装指定版本的包 | 一张假钞的真实世界 使用以下命令安装指定版本的包&#xff1a; # pip install pyspark2.3.3...

【pytest】获取所有用例名称并存于数据库

数据库操作包&#xff0c;引用前面创建的py文件&#xff0c;【sqlite】python操作sqlite3&#xff08;含测试&#xff09; #!/usr/bin/env python # -*- coding: utf-8 -*- # Time : 2025-02-11 8:45 # Author : duxiaowei # File : get_filename.py # Software: 这个文…...

Java中原子操作的实现原理

目录 一、处理器如何实现原子操作&#xff1f; 1.使用总线锁保证原子性 1.使用缓存锁保证原子性 二、Java如何实现原子操作&#xff1f; 1&#xff09;使用循环CAS实现原子操作 2&#xff09;CAS实现原子操作的三大问题 3&#xff09;使用锁机制实现原子操作 前言 原子&…...

25农村发展研究生复试面试问题汇总 农村发展专业知识问题很全! 农村发展复试全流程攻略 农村发展考研复试真题汇总

农村发展复试当然有好的建议&#xff01;前提是复试重点面试题背好&#xff01; 你是不是也在为农村发展考研复试发愁&#xff1f;担心自己准备不充分、表现不好&#xff1f;别急&#xff01;今天&#xff0c;学姐——复试面试拿下90分成功上岸的学姐&#xff0c;来给大家分享…...

一维前缀和与二维前缀和

前缀和&#xff08;Prefix Sum&#xff09;是一种用于高效计算数组区间和的预处理技术&#xff0c;尤其适用于需要频繁查询子数组或子矩阵和的场景。下面详细讲解一维前缀和与二维前缀和的原理、构建方法及应用。 一、一维前缀和 1. 定义 前缀和数组 prefix 的每个元素 prefi…...

3×2 MIMO系统和2×2 MIMO系统对比

从 SVD&#xff08;奇异值分解&#xff09;预编码 的角度分析&#xff0c;32 MIMO 系统相比 22 MIMO 系统在容量、功率分配灵活性和抗干扰能力方面具有潜在优势。以下是具体分析&#xff1a; 1. SVD预编码的基本原理 SVD 预编码是一种基于信道状态信息&#xff08;CSI&#xf…...

【MySQL — 数据库基础】深入解析 MySQL 的联合查询

1. 插入查询结果 语法 insert into table_name1 select* from table_name2 where restrictions ;注意&#xff1a;查询的结果集合&#xff0c;列数 / 类型 / 顺序 要和 insert into 后面的表相匹配&#xff1b;列的名字不要求相同&#xff1b; create table student1(id int , …...

【医院运营统计专题】3.解码医院运营统计:目标、原则与未来蓝图

医院成本核算、绩效管理、运营统计、内部控制、管理会计专题索引 一、医院运营统计的关键意义 在医疗行业持续发展与变革的大背景下,医院运营统计作为医院管理的关键组成部分,其重要性愈发凸显。从国内医院的普遍现状来看,运营统计已深度融入日常管理,为医院的有序运转提…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...