蓝桥杯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 中通常包含的…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
