蓝桥杯2023年第十四届省赛真题-买瓜--C语言题解
目录
蓝桥杯2023年第十四届省赛真题-买瓜
题目描述
输入格式
输出格式
样例输入
样例输出
提示
【思路解析】
【代码实现】
蓝桥杯2023年第十四届省赛真题-买瓜
时间限制: 3s 内存限制: 320MB 提交: 796 解决: 69
题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜,每个瓜的重量为 Ai 。
小蓝刀功了得,他可以把任何瓜劈成完全等重的两份,不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜,请输出 −1 。
输入格式
输入的第一行包含两个整数 n, m,用一个空格分隔,分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含 n 个整数 Ai,相邻整数之间使用一个空格分隔,分别表示每个瓜的重量。
输出格式
输出一行包含一个整数表示答案。
样例输入
复制
3 10 1 3 13
样例输出
复制
2
提示
对于 20% 的评测用例,∑n≤10;
对于 60% 的评测用例,∑n≤20;
对于所有评测用例,1 ≤n≤30,1≤ Ai ≤ 109 ,1 ≤ m ≤ 10^9
【思路解析】
这道题是一个很简单的递归可能性的罗列,但是每次递归有三个情况,则时间复杂度为O(3^N),时间复杂度过高,所以需要在递归过程中除掉那些完全不可能的解,使复杂度降低。
【代码实现】
#include<stdio.h>
int n = 0, m = 0, nums[30], min = 100;
long suf[31];
int dfs(int i, double sum, int c) {if (c >= min) return 100; // 劈瓜的次数大于等于最小值,即使能满足要求m也没有意义,因为它不是最小的if (sum == m) {min = c;return c;}if (sum > m) return 100; // 如果当前sum大于m,即可提前结束if (i == n) {return 100; //此时已经使用了所有西瓜,也无法满足,直接排除掉}if (suf[i] + sum < m) return 100; // 如果当前sum加上剩余所有值都小于m,即可提前结束int a = dfs(i + 1, sum + nums[i], c); // 全拿走 int b = dfs(i + 1, sum + (nums[i] / 2.0), c + 1); // 拿走一半 int f = dfs(i + 1, sum, c); // 不拿走 int k = mins(b, f);return mins(a, k);
}
int mins(int a, int b){return a > b? b :a;
}
int main(){scanf("%d %d", &n, &m);int i = 0;for (i = 0; i < n; i++) {scanf("%d", &nums[i]);}for (i = n - 1; i >= 0; i--) {suf[i] = suf[i + 1] + nums[i];}int m = dfs(0, 0, 0);if (m == 100)printf("-1");else{printf("%d\n",m);}return 0;
}
相关文章:
蓝桥杯2023年第十四届省赛真题-买瓜--C语言题解
目录 蓝桥杯2023年第十四届省赛真题-买瓜 题目描述 输入格式 输出格式 样例输入 样例输出 提示 【思路解析】 【代码实现】 蓝桥杯2023年第十四届省赛真题-买瓜 时间限制: 3s 内存限制: 320MB 提交: 796 解决: 69 题目描述 小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个…...
R语言进行孟德尔随机化+meta分析(1)---meta分析基础
目前不少文章用到了孟德尔随机化meta分析,今天咱们也来介绍一下,孟德尔随机化meta其实主要就是meta分析的过程,提取了孟德尔随机化文章的结果,实质上就是个meta分析,不过多个孟德尔随机化随机化的结果合并更加加强了结…...
网络安全第一次作业
1、什么是防火墙 防火墙是一种网络安全系统,它根据预先确定的安全规则监视和控制传入和传出的网络流量。其主要目的是阻止对计算机或网络的未经授权的访问,同时允许合法通信通过。 防火墙可以在硬件、软件或两者的组合中实现,并且可以配置为根…...
idea设置gradle
1、不选中 2、下面选specified location 指定gradle目录...
基于Elasticsearch的多文档检索 比如 商品(goods)、案例(cases)
概述 Elasticsearch多文档聚合检索 详细 记得把这几点描述好咯:需求(要做什么) 代码实现过程 项目文件结构截图 演示效果 应用场景 我们需要在五种不同的文档中检索数据。 比如 商品(goods)、案例(ca…...
9月18日,每日信息差
今天是2023年09月19日,以下是为您准备的11条信息差 第一、江苏无锡首次获得6000年前古人类DNA 第二、全球天然钻石价格暴跌。数据显示,国际钻石交易所钻石价格指数在2022年3月达到158的历史峰值,之后一路下跌到目前的110左右,创…...
基于FPGA实现FPDLINK III
功能概述 本模块主要包含FPDLINKIII/CML收发信号与HDMI/SDI/USB信号、千兆网络信号,支持客户按照按照指定功能定制 当前默认功能为FPD LINK III/CML转为HDMI/SDI/UVC信号 性能参数 名称 描述 供电接口 DC12V FPD LINK RX GM8914 FPD LINK TX GM8913 千兆网…...
[补题记录] Atcoder Beginner Contest 309(E)
URL:https://atcoder.jp/contests/abc309 目录 E Problem/题意 Thought/思路 解法一: 解法二: Code/代码 E Problem/题意 一个家庭有 N 个人,根节点为 1,给出 2 ~ N 的父节点。一共购买 M 次保险,每…...
【HarmonyOS】解决API6 WebView跳转外部浏览器问题、本地模拟器启动黑屏
【问题描述1】 HarmonyOS API6 Java开发中使用WebView组件,如果网页中有跳转链接,点击会跳转到手机系统浏览器。 【解决方案】 解决这个问题的方法就是给WebView这种自定义的WebAgent对象。具体代码如下: WebConfig webConfigthis.webView…...
给出三个整数,判断大小
7-2 比较大小 给出三个整数,判断大小。 输入格式: 给出三个整数a,b,c 输出格式: 在一行中依次从小到大的顺序输出,两数之间有一个空格,无多余空格。 输入样例: 在这里给出一组输入。例如: 2 1 5 输出样例: 在这里给出相应的输…...
优化软件系统,解决死锁问题,提升稳定性与性能 redis排队下单
项目背景: 随着用户数量的不断增加,我们的速卖通小管家软件系统面临了一个日益严重的问题:在从存储区提供程序的数据读取器中进行读取时,频繁出现错误。系统报告了一个内部异常: 异常信息如下: 从存储区提供程序的数…...
MyBatisPlus 底层用 json 存储,Java 仍然使用 对象操作
PO 类的字段定义为一个对象,然后使用以下注解修饰 TableField(typeHandler JacksonTypeHandler.class) 当然 jsonTypeHandler 有多种可以选择...
发送验证码倒计时 防刷新重置!!!
需求:发送验证码,每60s可点击发送一次,倒计时中按钮不可点击,且刷新页面倒计时不会重置 可用以下方式避免刷新页面时,倒计时重置 localStorage本地缓存方式 思路: 1.记录倒计时的时间 2.页面加载时&…...
OpenCV项目开发实战--forEach的并行像素访问与其它方法的性能比较
在本教程中,我们将比较Mat 类的forEach方法与 OpenCV 中访问和转换像素值的其他方法的性能。我们将展示forEach如何比简单地使用at方法甚至有效地使用指针算术快得多。 OpenCV 内部有一些隐藏的宝石,有时并不为人所知。这些隐藏的宝石之一是Mat 类的forEach方法,它利用计算…...
cv::Mat 的常见操作方法
cv::Mat是OpenCV库中用于处理图像和矩阵的主要数据结构。以下是一些常见的cv::Mat操作方法: 创建和初始化 cv::Mat::Mat(): 创建一个空的cv::Mat对象。cv::Mat::Mat(int rows, int cols, int type): 创建一个指定行数、列数和数据类型的cv::Mat对象。cv::Mat::Mat(i…...
JVM——11.JVM小结
这篇文章我们来小结一下JVM JVM,即java虚拟机,是java代码运行时的环境。我们从底层往上层来说,分别是硬件部分,操作系统,JVM,jre,JDK,java代码。JVM是直接与操作系统打交道的。JVM也…...
月木学途开发 2.前台用户模块
概述 效果展 数据库设计 会员表 DROP TABLE IF EXISTS user_type; CREATE TABLE user_type (userTypeId int(11) NOT NULL AUTO_INCREMENT,userTypeName varchar(255) DEFAULT NULL,userTypeDesc varchar(255) DEFAULT NULL,PRIMARY KEY (userTypeId) ) ENGINEInnoDB AUTO_I…...
buuctf-ciscn_s_3
一、srop 参考文章-博客园-wudiiv11(作者)-BUUCTF-ciscn_2019_s_3 参考文章-博客园-z2yh(作者)-Srop 原理与利用方法 vlun函数中没有分配栈帧(指rsp没有增长,也没有压入父函数的rbp,这也导致…...
3D模型格式转换工具HOOPS Exchange协助Epic Games实现CAD数据轻松导入虚幻引擎
一、面临的挑战 Epic Games最为人所知的身份可能是广受欢迎的在线视频游戏Fortnite的开发商,但它也是虚幻引擎背后的团队,虚幻引擎是一种实时3D创作工具,为世界领先的游戏提供动力,并且也被电影电视、建筑、汽车、制造、模拟等领…...
Linux- inode vnode
什么是inode inode 是 UNIX 和 UNIX-like 操作系统中的一个关键概念。它代表了文件系统中文件或目录的元数据。每个文件和目录在文件系统中都有一个与之关联的 inode。这个数据结构存储了关于文件的所有信息,除了其名称和实际数据之外。 以下是 inode 中通常包含的…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
