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

蓝桥杯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 个瓜&#xff0c;每个瓜的重量为 Ai 。 小蓝刀功了得&#xff0c;他可以把任何瓜劈成完全等重的两份&#xff0c;不过每个瓜只能劈一刀。 小蓝希望买到的瓜的重量的和恰好为 m 。 请问小蓝至少要劈多少个瓜才能买到重量恰好…...

生成式人工智能服务安全基本要求实务解析

本文尝试明晰《基本要求》的出台背景与实践定位&#xff0c;梳理《基本要求》所涉的各类安全要求&#xff0c;以便为相关企业遵循执行《基本要求》提供抓手。 引言 自2022年初以来&#xff0c;我国陆续发布算法推荐、深度合成与生成式人工智能服务相关的规范文件&#xff0c;…...

nginx详解,配置http,https,负载均衡,反向代理,SMTP 代理步骤说明

Nginx 是一款高性能的开源 Web 服务器,同时也可以用作反向代理服务器、负载均衡器、HTTP 缓存、HTTPS 中继、以及作为邮件代理服务器等。以下是 Nginx 可以实现的一些常见用途: 静态内容服务: Nginx 可以用来提供静态内容,比如 HTML、CSS、JavaScript 文件等。 动态内容服务…...

ARTS Week 20

Algorithm 本周的算法题为 1222. 可以攻击国王的皇后 在一个 下标从 0 开始 的 8 x 8 棋盘上&#xff0c;可能有多个黑皇后和一个白国王。 给你一个二维整数数组 queens&#xff0c;其中 queens[i] [xQueeni, yQueeni] 表示第 i 个黑皇后在棋盘上的位置。还给你一个长度为 2 的…...

python如何读取文件

这里的文件是txt文件&#xff0c;office文件不支持。 假如有一个pi_digits的txt文件&#xff0c;里面的内容是“3.1415926” 如果要读取这个文件的内容&#xff0c;需要调取pathlib模块&#xff0c;并把路径告知python。同时python文件必须要和目标读取文件在一个文件夹里。 …...

InnoDB和MyISAM存储引擎

InnoDB mysql默认存储引擎 支持事务&#xff0c;行级锁&#xff08;并发量大&#xff09;&#xff0c;外键约束&#xff0c;容量大&#xff0c;支持缓存&#xff0c;支撑主键自增&#xff0c; 全文检索&#xff0c;不存储表的总行数&#xff0c;需要sql逐行统计 MyISAM 不…...

DataGrip 2023:让数据库开发变得更简单、更高效 mac/win

JetBrains DataGrip 2023是一款功能强大的数据库IDE&#xff0c;专为数据库开发和管理而设计。通过DataGrip&#xff0c;您可以连接到各种关系型数据库管理系统(RDBMS)&#xff0c;并使用其提供的一组工具来查询、管理、编辑和开发数据库。 DataGrip 2023软件获取 DataGrip 2…...

突破编程_C++_设计模式(命令模式)

1 命令模式的基本概念 C 命令模式是一种设计模式&#xff0c;它允许将请求封装为一个对象&#xff0c;从而可以用不同的请求对客户进行参数化&#xff1b;对请求排队或记录请求日志&#xff0c;以及支持可撤销的操作。命令模式的主要目的是将请求封装为对象&#xff0c;从而可…...

LeetCode102题:二叉树的层序遍历(python3)

代码思路&#xff1a;使用队列先进先出的特性&#xff0c;queue[]不为空进入for循环&#xff0c;tmp存储每层的节点&#xff0c;将结果添加至res[]中。 python中使用collections中的双端队列deque()&#xff0c;其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 然后进入代码目录&#xff0c;git pull 会提示输入git账号、密码&#xff0c;因为我们提前输…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的田间杂草检测系统(深度学习模型+UI界面+Python代码+训练数据集)

摘要&#xff1a;开发用于田间杂草识别的系统对提高农业运营效率和提升作物产出至关重要。本篇文章详尽阐述了如何应用深度学习技术开发一个用于田间杂草识别的系统&#xff0c;并附上了完备的代码实现。该系统基于先进的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLOv5…...

java Lambda表达式如何支持静态方法引用

java Lambda表达式如何支持静态方法引用 在Java中&#xff0c;Lambda表达式支持静态方法引用&#xff0c;允许你直接使用静态方法作为Lambda表达式的实现。静态方法引用使用类名和方法名来引用静态方法。 下面是一个简单的示例&#xff0c;展示了如何在Lambda表达式中使用静态…...

SpringMVC04、Controller 及 RestFul

4、Controller 及 RestFul 4.1、控制器Controller 控制器复杂提供访问应用程序的行为&#xff0c;通常通过接口定义或注解定义两种方法实现。控制器负责解析用户的请求并将其转换为一个模型。在Spring MVC中一个控制器类可以包含多个方法在Spring MVC中&#xff0c;对于Contr…...

【机器学习300问】33、决策树是如何进行特征选择的?

还记得我在【机器学习300问】的第28问里谈到的&#xff0c;看决策树的定义不就是if-else语句吗怎么被称为机器学习模型&#xff1f;其中最重要的两点就是决策树算法要能够自己回答下面两问题&#xff1a; 该选哪些特征 特征选择该选哪个阈值 阈值确定 今天这篇文章承接上文&…...

剑指offer C ++双栈实现队列

1. 基础 队列&#xff1a;先进先出&#xff0c;即插入数据在队尾进行&#xff0c;删除数据在队头进行&#xff1b; 栈&#xff1a;后进先出&#xff0c;即插入与删除数据均在栈顶进行。 2. 思路 两个栈实现一个队列的思想&#xff1a;用pushStack栈作为push数据的栈&#xff…...

【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 模型导出&#xff08;补充内容&#xff09;4…...

Zookeeper搭建

目录 前言 初了解Zookeeper 搭建 准备 配置Zookeeper 前言 今天来介绍Zookeeper的搭建&#xff0c;其实Zookeeper的搭建很简单&#xff0c;但是为什么还要单独整一节呢&#xff0c;这就不得不先了解Zookeeper有什么功能了&#xff01;而且现在很火的框架也离不开Zookeepe…...

2.Datax数据同步之Windows下,mysql和sqlserver之间的自定义sql文数据同步

目录 前言步骤操作大纲步骤明细mysql 至 sqlServersqlServer 至 mysql执行同步语句中报 前言 上一篇文章实现了不同的mysql数据库之间的数据同步&#xff0c;在此基础上本篇将实现mysql和sqlserver之间的自定义sql文数据同步 准备工作&#xff1a; JDK(1.8以上&#xff0c;推…...

commonjs和esmodule

commonjs的模块导出和引用写法&#xff1a; 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的编译系统

安卓的编译真的太多吐槽的地方了&#xff0c;有必须到croot下编译的&#xff0c;有随便改个.c就要七八分钟编译的。我有时候真的不知道这么多开发人员是怎么挺过来的。 今晚简单看看这个编译系统soong吧。 算了&#xff0c;下面这个写的很好了&#xff0c;我先看看吧。。。 …...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...