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

蓝桥杯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分析&#xff0c;今天咱们也来介绍一下&#xff0c;孟德尔随机化meta其实主要就是meta分析的过程&#xff0c;提取了孟德尔随机化文章的结果&#xff0c;实质上就是个meta分析&#xff0c;不过多个孟德尔随机化随机化的结果合并更加加强了结…...

网络安全第一次作业

1、什么是防火墙 防火墙是一种网络安全系统&#xff0c;它根据预先确定的安全规则监视和控制传入和传出的网络流量。其主要目的是阻止对计算机或网络的未经授权的访问&#xff0c;同时允许合法通信通过。 防火墙可以在硬件、软件或两者的组合中实现&#xff0c;并且可以配置为根…...

idea设置gradle

1、不选中 2、下面选specified location 指定gradle目录...

基于Elasticsearch的多文档检索 比如 商品(goods)、案例(cases)

概述 Elasticsearch多文档聚合检索 详细 记得把这几点描述好咯&#xff1a;需求&#xff08;要做什么&#xff09; 代码实现过程 项目文件结构截图 演示效果 应用场景 我们需要在五种不同的文档中检索数据。 比如 商品&#xff08;goods&#xff09;、案例&#xff08;ca…...

9月18日,每日信息差

今天是2023年09月19日&#xff0c;以下是为您准备的11条信息差 第一、江苏无锡首次获得6000年前古人类DNA 第二、全球天然钻石价格暴跌。数据显示&#xff0c;国际钻石交易所钻石价格指数在2022年3月达到158的历史峰值&#xff0c;之后一路下跌到目前的110左右&#xff0c;创…...

基于FPGA实现FPDLINK III

功能概述 本模块主要包含FPDLINKIII/CML收发信号与HDMI/SDI/USB信号、千兆网络信号&#xff0c;支持客户按照按照指定功能定制 当前默认功能为FPD LINK III/CML转为HDMI/SDI/UVC信号 性能参数 名称 描述 供电接口 DC12V FPD LINK RX GM8914 FPD LINK TX GM8913 千兆网…...

[补题记录] Atcoder Beginner Contest 309(E)

URL&#xff1a;https://atcoder.jp/contests/abc309 目录 E Problem/题意 Thought/思路 解法一&#xff1a; 解法二&#xff1a; Code/代码 E Problem/题意 一个家庭有 N 个人&#xff0c;根节点为 1&#xff0c;给出 2 ~ N 的父节点。一共购买 M 次保险&#xff0c;每…...

【HarmonyOS】解决API6 WebView跳转外部浏览器问题、本地模拟器启动黑屏

【问题描述1】 HarmonyOS API6 Java开发中使用WebView组件&#xff0c;如果网页中有跳转链接&#xff0c;点击会跳转到手机系统浏览器。 【解决方案】 解决这个问题的方法就是给WebView这种自定义的WebAgent对象。具体代码如下&#xff1a; WebConfig webConfigthis.webView…...

给出三个整数,判断大小

7-2 比较大小 给出三个整数&#xff0c;判断大小。 输入格式: 给出三个整数a,b,c 输出格式: 在一行中依次从小到大的顺序输出&#xff0c;两数之间有一个空格&#xff0c;无多余空格。 输入样例: 在这里给出一组输入。例如&#xff1a; 2 1 5 输出样例: 在这里给出相应的输…...

优化软件系统,解决死锁问题,提升稳定性与性能 redis排队下单

项目背景&#xff1a; 随着用户数量的不断增加&#xff0c;我们的速卖通小管家软件系统面临了一个日益严重的问题&#xff1a;在从存储区提供程序的数据读取器中进行读取时&#xff0c;频繁出现错误。系统报告了一个内部异常: 异常信息如下&#xff1a; 从存储区提供程序的数…...

MyBatisPlus 底层用 json 存储,Java 仍然使用 对象操作

PO 类的字段定义为一个对象&#xff0c;然后使用以下注解修饰 TableField(typeHandler JacksonTypeHandler.class) 当然 jsonTypeHandler 有多种可以选择...

发送验证码倒计时 防刷新重置!!!

需求&#xff1a;发送验证码&#xff0c;每60s可点击发送一次&#xff0c;倒计时中按钮不可点击&#xff0c;且刷新页面倒计时不会重置 可用以下方式避免刷新页面时&#xff0c;倒计时重置 localStorage本地缓存方式 思路&#xff1a; 1.记录倒计时的时间 2.页面加载时&…...

OpenCV项目开发实战--forEach的并行像素访问与其它方法的性能比较

在本教程中,我们将比较Mat 类的forEach方法与 OpenCV 中访问和转换像素值的其他方法的性能。我们将展示forEach如何比简单地使用at方法甚至有效地使用指针算术快得多。 OpenCV 内部有一些隐藏的宝石,有时并不为人所知。这些隐藏的宝石之一是Mat 类的forEach方法,它利用计算…...

cv::Mat 的常见操作方法

cv::Mat是OpenCV库中用于处理图像和矩阵的主要数据结构。以下是一些常见的cv::Mat操作方法&#xff1a; 创建和初始化 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&#xff0c;即java虚拟机&#xff0c;是java代码运行时的环境。我们从底层往上层来说&#xff0c;分别是硬件部分&#xff0c;操作系统&#xff0c;JVM&#xff0c;jre&#xff0c;JDK&#xff0c;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&#xff08;作者&#xff09;-BUUCTF-ciscn_2019_s_3 参考文章-博客园-z2yh&#xff08;作者&#xff09;-Srop 原理与利用方法 vlun函数中没有分配栈帧&#xff08;指rsp没有增长&#xff0c;也没有压入父函数的rbp&#xff0c;这也导致…...

3D模型格式转换工具HOOPS Exchange协助Epic Games实现CAD数据轻松导入虚幻引擎

一、面临的挑战 Epic Games最为人所知的身份可能是广受欢迎的在线视频游戏Fortnite的开发商&#xff0c;但它也是虚幻引擎背后的团队&#xff0c;虚幻引擎是一种实时3D创作工具&#xff0c;为世界领先的游戏提供动力&#xff0c;并且也被电影电视、建筑、汽车、制造、模拟等领…...

Linux- inode vnode

什么是inode inode 是 UNIX 和 UNIX-like 操作系统中的一个关键概念。它代表了文件系统中文件或目录的元数据。每个文件和目录在文件系统中都有一个与之关联的 inode。这个数据结构存储了关于文件的所有信息&#xff0c;除了其名称和实际数据之外。 以下是 inode 中通常包含的…...

不来看看?通过Python实现贪吃蛇小游戏

&#x1f3c5;我是默&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;在这里&#xff0c;我要推荐给大家我的专栏《Python》。&#x1f3af;&#x1f3af; &#x1f680;无论你是编程小白&#xff0c;还是有一定基础的程序员&#xff0c;这个专…...

C# linq初探 使用linq查询数组中元素

使用linq进行数组查询 输出数组中全部的偶数并升序输出结果 写法1&#xff1a; int[] numbers { 5, 10, 8, 3, 6, 12 }; //查询的数组var numqurey from num in numberswhere num % 2 0 //按照条件过滤orderby numselect num;foreach (var num in numqurey){Console.Writ…...

使用线程池进行任务处理

线程池 线程池&#xff1a;一种线程使用模式。线程过多会带来调度开销&#xff0c;进而影响缓存局部性和整体性能。而线程池维护着多个线程&#xff0c;等待着监督管理者分配可并发执行的任务。这避免了在处理短时间任务时创建与销毁线程的代价。线程池不仅能够保证内核的充分…...

ES6之Map和Set有什么不同?

一、Map 1.定义 Map是ES6提供的一种新的数据结构&#xff0c;它是键值对的集合&#xff0c;类似于对象&#xff0c;但是键的范围不限于字符串&#xff0c;各种类型的值都可以当做键。 Object结构是“字符串-值”的对应&#xff0c;Map结构则是“值-值”的对应 2.代码示例 M…...

Java中的集合

Java中的集合分为单列集合和双列集合&#xff0c;单列集合顶级接口为Collection&#xff0c;双列集合顶级接口为Map。 Collection 的子接口有两个&#xff1a;List和Set。 List 接口的特点&#xff1a;元素可重复&#xff0c;有序&#xff08;存取顺序&#xff09;。 List 接…...

9.4.2servlet基础2

一.SmartTomcat 1.第一次使用需要进行配置. 二.异常处理 1.404:浏览器访问的资源,在服务器上不存在. a.检查请求的路径和服务器配置的是否一致(大小写,空格,标点符号). b. 确认webapp是否被正确加载(检查web.xml没有/目录错误/内容错误/名字拼写错误)(多多关注日志信息). 2…...

嵌入式学习 - 用电控制电

目录 前言&#xff1a; 1、继电器 2、二极管 3、三极管 3.1 特殊的三极管-mos管 3.2 npn类型三极管 3.3 pnp类型三极管 3.4 三极管的放大特性 3.5 mos管和三极管的区别 前言&#xff1a; 计算机的工作的核心原理&#xff1a;用电去控制电。 所有的电子元件都有数据手册…...

QCA组态如何科学命名?

前言 &#xff08;一&#xff09;文献来源 文献来源&#xff1a;[1]Furnari S, Crilly D, Misangyi V F, et al. Capturing causal complexity: Heuristics for configurational theorizing[J]. Academy of Management Review, 2021, 46(4): 778-799. &#xff08;二&#xff…...

外贸行业中常用的邮箱推荐

随着全球贸易的不断发展&#xff0c;外贸行业越来越重要。在这个过程中&#xff0c;电子邮件作为一种重要的沟通工具&#xff0c;扮演着关键的角色。然而&#xff0c;对于许多外贸从业者来说&#xff0c;选择合适的邮箱服务并不容易。本文将探讨外贸邮箱和普通邮箱的区别&#…...

高性能实践

1、认识性能 从用户体验来看&#xff0c;性能就是响应时间短&#xff1b; 从开发角度来看&#xff0c;性能主要是执行效率高。 性能主要表现形式如下&#xff1a; &#xff08;1&#xff09;响应时间&#xff0c;AVG、MAX、MIN、TP95、TP99 &#xff08;2&#xff09;吞吐…...

网站突然显示 建设中/微信营销软件哪个好用

m_Orchestrate learning system---十二、为什么thinkphp验证场景里面的多个属性之间是逗号一、总结一句话总结&#xff1a;因为是数组啊1 protected $scene [2 edit > [name,age],3 ];1、原生js如何获取html内容&#xff1f;1 2 functioncheck(){3 varrepassworddocument.g…...

做网站赚多少/微信上如何投放广告

什么是正则表达式正则表达式是一种工具&#xff0c;和其他工具一样&#xff0c;它是人们为了解决特定的问题而发明的&#xff0c;主要有两种用途&#xff1a;一种是查找特定的信息&#xff08;搜索&#xff09;另一种是查找并编辑特定的信息&#xff08;替换&#xff09;它是文…...

号号网站开发/百度seo费用

雨的印记原名Kiss The Rain&#xff0c;这首曲子出自韩国最擅长描绘爱情的音乐家李闰珉(YIRUMA)之手&#xff0c;写这首歌的时候&#xff0c;是在一个星星满天的夜晚&#xff0c;忽然间一场雨&#xff0c;让YIRUMA有感而发写下Kiss The Rain这首曲子。中文名称雨的印记外文名称…...

别人盗用我的网站备案号怎么办/php开源建站系统

学了几天的python和FME Objects&#xff0c;发现之间教程里的很多对象已经过时了&#xff0c;而且语法和vb相差比较大&#xff0c;但概念还是一样的&#xff0c;下面写一段python代码&#xff0c;将这几天学习的对象联系一下&#xff0c;下面的代码功能是读schema feature和dat…...

密云住房和城乡建设部网站首页/培训机构哪家好

这些题目都是大一刚入学时学习C语言的课后作业&#xff0c;在OJ上看到还保留着&#xff0c;就都整理下发出来吧......(只有题和代码)【问题描述】编写程序&#xff0c;打开一篇英文文章(存在当前目录下的文件in.txt中)&#xff0c;为该文章生成词汇表(存到当前目录下的另一个文…...

网站开发的职责/百度seo点击器

使用ip a命令查看虚拟机的网卡信息 发现有一个虚拟网卡virbr0 [rootlocalhost ~]# ip a 1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00inet 127.0.0.1/8 scope…...