蓝桥杯2023年-买瓜(dfs,类型转换同样耗时)
题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜,每个瓜的重量为 Ai 。
小蓝刀功了得,他可以把任何瓜劈成完全等重的两份,不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜,请输出 −1 。
思路
朴素做法:
dfs每个瓜,有三种选择:
1.选瓜
2.劈瓜,选瓜
3.不选瓜
则复杂度为3^n,也就是3^30,大概2e14,绝对会超时。
所以需要剪枝优化
剪枝优化:
1.如果当前已有重量>所需重量,则剪枝
2.如果当前已有重量+剩下的重量总和<所需重量,剪枝,(求剩下的重量可以用后缀和数组优化)
3.如果当前已经劈过的次数>=目前的劈瓜的最小次数,剪枝
细枝末节:
还有一些细枝末节可优化:
1.除2的话可能会有小数,但是浮点数运算会慢很多,所以我们可以通过放大(乘2)原重量与所需重量。这样就可以只使用整型运算了。(也可以用两个数组分别存储放大后的重量与相应的减半的数量,这样可以在每次搜索时减少一次运算,不过应该影响不大)
2.将重量从大到小排序,这样可以提前排除许多剪枝。
3.强制类型转换的耗时也不少。(int转long之类的)(这一点是我没有想到的,也是我卡题的原因,经过不断不断一直一直反反复复的比对题解代码后才发现的。)
大家可以感受一下:
有转换的耗时,结果超时一半多
#include<bits/stdc++.h>
using namespace std;
int a[33];//原重
int b[33];//半重
long latter[33];
int m;
int n;
int ans=100;
void dfs(int u,int sum,int k){//sum为int类型时,long与int进行加减时会进行一次类型转换if(u==n||sum>=m||k>=ans||latter[u]+sum<m){if(sum==m)ans=min(ans,k);return ;}dfs(u+1,sum+a[u],k);dfs(u+1,sum+b[u],k+1);dfs(u+1,sum,k);
}
int main()
{cin>>n>>m;m*=2;for(int i=0;i<n;i++){cin>>b[i];a[i]=b[i]*2;}sort(a,a+n,greater<int>());sort(b,b+n,greater<int>());for(int i=n-1;i>=0;i--)latter[i]=latter[i+1]+a[i];dfs(0,0,0);if(ans!=100)cout<<ans;else cout<<-1;
}

没有类型转换的,成功通过,二者时间整整相差一倍:
#include<bits/stdc++.h>
using namespace std;
int a[33];//原重
int b[33];//半重
long latter[33];
int m;
int n;
int ans=100;
void dfs(int u,long sum,int k){//sum为long类型时,没有类型转换的耗时if(u==n||sum>=m||k>=ans||latter[u]+sum<m){if(sum==m)ans=min(ans,k);return ;}dfs(u+1,sum+a[u],k);dfs(u+1,sum+b[u],k+1);dfs(u+1,sum,k);
}
int main()
{cin>>n>>m;m*=2;for(int i=0;i<n;i++){cin>>b[i];a[i]=b[i]*2;}sort(a,a+n,greater<int>());sort(b,b+n,greater<int>());for(int i=n-1;i>=0;i--)latter[i]=latter[i+1]+a[i];dfs(0,0,0);if(ans!=100)cout<<ans;else cout<<-1;
}

也不排除是测评机的原因,不过以后最好还是减少类似的类型转换更保险一些。
相关文章:
蓝桥杯2023年-买瓜(dfs,类型转换同样耗时)
题目描述 小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜,每个瓜的重量为 Ai 。 小蓝刀功了得,他可以把任何瓜劈成完全等重的两份,不过每个瓜只能劈一刀。 小蓝希望买到的瓜的重量的和恰好为 m 。 请问小蓝至少要劈多少个瓜才能买到重量恰好…...
生成式人工智能服务安全基本要求实务解析
本文尝试明晰《基本要求》的出台背景与实践定位,梳理《基本要求》所涉的各类安全要求,以便为相关企业遵循执行《基本要求》提供抓手。 引言 自2022年初以来,我国陆续发布算法推荐、深度合成与生成式人工智能服务相关的规范文件,…...
nginx详解,配置http,https,负载均衡,反向代理,SMTP 代理步骤说明
Nginx 是一款高性能的开源 Web 服务器,同时也可以用作反向代理服务器、负载均衡器、HTTP 缓存、HTTPS 中继、以及作为邮件代理服务器等。以下是 Nginx 可以实现的一些常见用途: 静态内容服务: Nginx 可以用来提供静态内容,比如 HTML、CSS、JavaScript 文件等。 动态内容服务…...
ARTS Week 20
Algorithm 本周的算法题为 1222. 可以攻击国王的皇后 在一个 下标从 0 开始 的 8 x 8 棋盘上,可能有多个黑皇后和一个白国王。 给你一个二维整数数组 queens,其中 queens[i] [xQueeni, yQueeni] 表示第 i 个黑皇后在棋盘上的位置。还给你一个长度为 2 的…...
python如何读取文件
这里的文件是txt文件,office文件不支持。 假如有一个pi_digits的txt文件,里面的内容是“3.1415926” 如果要读取这个文件的内容,需要调取pathlib模块,并把路径告知python。同时python文件必须要和目标读取文件在一个文件夹里。 …...
InnoDB和MyISAM存储引擎
InnoDB mysql默认存储引擎 支持事务,行级锁(并发量大),外键约束,容量大,支持缓存,支撑主键自增, 全文检索,不存储表的总行数,需要sql逐行统计 MyISAM 不…...
DataGrip 2023:让数据库开发变得更简单、更高效 mac/win
JetBrains DataGrip 2023是一款功能强大的数据库IDE,专为数据库开发和管理而设计。通过DataGrip,您可以连接到各种关系型数据库管理系统(RDBMS),并使用其提供的一组工具来查询、管理、编辑和开发数据库。 DataGrip 2023软件获取 DataGrip 2…...
突破编程_C++_设计模式(命令模式)
1 命令模式的基本概念 C 命令模式是一种设计模式,它允许将请求封装为一个对象,从而可以用不同的请求对客户进行参数化;对请求排队或记录请求日志,以及支持可撤销的操作。命令模式的主要目的是将请求封装为对象,从而可…...
LeetCode102题:二叉树的层序遍历(python3)
代码思路:使用队列先进先出的特性,queue[]不为空进入for循环,tmp存储每层的节点,将结果添加至res[]中。 python中使用collections中的双端队列deque(),其popleft()方法可达到O(1)时间复杂度。 class Solution:def lev…...
linux服务器保存git账号密码命令
1.保存git账号密码 git config --global credential.helper store 2.查看git账号密码 cd回车 ls -a cat .git-credentials 步骤: 先输入 git config --global credential.helper store 然后进入代码目录,git pull 会提示输入git账号、密码,因为我们提前输…...
基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的田间杂草检测系统(深度学习模型+UI界面+Python代码+训练数据集)
摘要:开发用于田间杂草识别的系统对提高农业运营效率和提升作物产出至关重要。本篇文章详尽阐述了如何应用深度学习技术开发一个用于田间杂草识别的系统,并附上了完备的代码实现。该系统基于先进的YOLOv8算法,并对比了YOLOv7、YOLOv6、YOLOv5…...
java Lambda表达式如何支持静态方法引用
java Lambda表达式如何支持静态方法引用 在Java中,Lambda表达式支持静态方法引用,允许你直接使用静态方法作为Lambda表达式的实现。静态方法引用使用类名和方法名来引用静态方法。 下面是一个简单的示例,展示了如何在Lambda表达式中使用静态…...
SpringMVC04、Controller 及 RestFul
4、Controller 及 RestFul 4.1、控制器Controller 控制器复杂提供访问应用程序的行为,通常通过接口定义或注解定义两种方法实现。控制器负责解析用户的请求并将其转换为一个模型。在Spring MVC中一个控制器类可以包含多个方法在Spring MVC中,对于Contr…...
【机器学习300问】33、决策树是如何进行特征选择的?
还记得我在【机器学习300问】的第28问里谈到的,看决策树的定义不就是if-else语句吗怎么被称为机器学习模型?其中最重要的两点就是决策树算法要能够自己回答下面两问题: 该选哪些特征 特征选择该选哪个阈值 阈值确定 今天这篇文章承接上文&…...
剑指offer C ++双栈实现队列
1. 基础 队列:先进先出,即插入数据在队尾进行,删除数据在队头进行; 栈:后进先出,即插入与删除数据均在栈顶进行。 2. 思路 两个栈实现一个队列的思想:用pushStack栈作为push数据的栈ÿ…...
【YOLOv9】训练模型权重 YOLOv9.pt 重新参数化轻量转为 YOLOv9-converted.pt
【YOLOv9】训练模型权重 YOLOv9.pt 重新参数化轻量转为 YOLOv9-converted.pt 1. 模型权重准备2. 模型重新参数化2.1 文件准备2.2 参数修改2.3 重新参数化过程 3. 重新参数化后模型推理3.1 推理超参数配置3.2 模型推理及对比 4. onnx 模型导出(补充内容)4…...
Zookeeper搭建
目录 前言 初了解Zookeeper 搭建 准备 配置Zookeeper 前言 今天来介绍Zookeeper的搭建,其实Zookeeper的搭建很简单,但是为什么还要单独整一节呢,这就不得不先了解Zookeeper有什么功能了!而且现在很火的框架也离不开Zookeepe…...
2.Datax数据同步之Windows下,mysql和sqlserver之间的自定义sql文数据同步
目录 前言步骤操作大纲步骤明细mysql 至 sqlServersqlServer 至 mysql执行同步语句中报 前言 上一篇文章实现了不同的mysql数据库之间的数据同步,在此基础上本篇将实现mysql和sqlserver之间的自定义sql文数据同步 准备工作: JDK(1.8以上,推…...
commonjs和esmodule
commonjs的模块导出和引用写法: lib.js 导出一个模块 let a 1 let b 2 function aPlus1() {return a } module.exports {a,b,aPlus1 } index.js引用一个模块 const {a,b,aPlus1} require(./lib.js) console.log(hh:,a) esmodule的模块导出和引用方法&#x…...
Android的编译系统
安卓的编译真的太多吐槽的地方了,有必须到croot下编译的,有随便改个.c就要七八分钟编译的。我有时候真的不知道这么多开发人员是怎么挺过来的。 今晚简单看看这个编译系统soong吧。 算了,下面这个写的很好了,我先看看吧。。。 …...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
