当前位置: 首页 > 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 中通常包含的…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...