小信砍柴的题解
目录
原题描述:
时间:1s 空间:256M
题目描述:
输入格式:
输出格式:
样例1输入:
题目大意:
主要思路:
注意事项:
总代码:
原题描述:
时间:1s 空间:256M
题目描述:
小信家里有段木材,初始长度表示为数组
。他可以进行以下填补操作至多
次(可以不操作):
选择两段木材,将
长度截
补到
上,即操作后
,
。
填补操作后,小信要将木材都砍成相同长度的小段,并且不能有剩余,请你告诉他最长的小段能有多长?
输入格式:
第一行包含两个整数表示木材数和操作数。
第二行包含个整数
,表示每段木材的初始长度。
输出格式:
输出一个整数,表示最长的小段的长度。
样例1输入:
2 1
15 9
样例1输出:
8
样例2输入:
2 10
15 9
样例2输出:
24
约定与提示:
对于100%的数据,。
样例1解释:选择操作之后序列变成
,能切成
根长度为
的木材。
样例2解释:选择 操作
次之后序列变成
,能切成
根长度为
的木材。
题目大意:
就是给你一个数组,然你可以操作最多m次,每次操作可以将一个数-1,另一个数+1,最后问你所有数的最大共约数(就是gcd)
主要思路:
直接上思维导图:

说一下几个重点,给上代码片段:
- 求因数:
int cnt=0;//数组下标 for(int i=1;i*i<=sum;i++)//只要枚举到(sqrt(sum)就可以了 {if(sum%i == 0)//如果是因数 {factor[cnt++] = i;//用来记录因数,放入因数数组中 if(i*i!=sum)//如果不是sum的平方根 {factor[cnt++] = sum/i;//sum/i也是sum的因数 }} } - 将小的补给大的:
int t=0;//记录花费次数 int pos=1;//记录从哪个小的开始补(就是被减的) for(int i=n;i>=1;i--)//枚举大的 {if(b[i]!=0)//如果不是大的(也可以这么理解(被用光了) {int x=f-b[i];//记录要消耗的次数(也是要被补多少) t+=x;//计入次数 while(x>0)//如果还需要补 {if(b[pos]>=x)//如果小的可以补完 {b[pos]-=x;//就补了 break;//跳出 }else{x-=b[pos];//否则就消耗一些要补的 b[pos] = 0;//把小的设成0pos++;//就让下一个小的来补 }}} } /* 直接看不太好看,我演示一遍。当f = 8,b数组为:{1,2,5},pos=1; 先枚举到5。t+=3, x=3。 开始补 第一次发现不可以全补完。 b[pos]也就是b[1]<3,那就耗掉一些。b[1] = 0,x=2,pos=2。 第二次发现可以补完,那就补完,b[2]-=2就是0,跳出。 此时的b数组为:{0,0,5} i枚举到 2时,b[2] == 0了,也就是被用光了,那就跳过。 i枚举到 1时,b[1] == 0了,也就是被用光了,那就跳过。 现在应该理解了吧。 */
注意事项:
不要把check中的b写成a了哦。
第一个合法因数输出后要return 0;
总代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[510];
int b[510];
int sum;
int factor[10010];//用来记录因数
bool check(int f)
{//千万不要把b写成afor(int i=1;i<=n;i++){b[i] = a[i]%f;}sort(b+1,b+1+n);int t=0;//记录花费次数 int pos=1;//记录从哪个小的开始补(就是被减的) for(int i=n;i>=1;i--)//枚举大的 {if(b[i]!=0)//如果不是大的(也可以这么理解(被用光了) {int x=f-b[i];//记录要消耗的次数(也是要被补多少) t+=x;//计入次数 while(x>0)//如果还需要补 {if(b[pos]>=x)//如果小的可以补完 {b[pos]-=x;//就补了 break;//跳出 }else{x-=b[pos];//否则就消耗一些要补的 b[pos] = 0;//把小的设成0pos++;//就让下一个小的来补 }}}}/*直接看不太好看,我演示一遍。当f = 8,b数组为:{1,2,5},pos=1; 先枚举到5。t+=3, x=3。开始补第一次发现不可以全补完。b[pos]也就是b[1]<3,那就耗掉一些。b[1] = 0,x=2,pos=2。 第二次发现可以补完,那就补完,b[2]-=2就是0,跳出。此时的b数组为:{0,0,5}i枚举到 2时,b[2] == 0了,也就是被用光了,那就跳过。 i枚举到 1时,b[1] == 0了,也就是被用光了,那就跳过。现在应该理解了吧。 */ return t<=m;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}int cnt=0;//数组下标 for(int i=1;i*i<=sum;i++)//只要枚举到(sqrt(sum)就可以了 {if(sum%i == 0)//如果是因数 {factor[cnt++] = i;//放入因数数组中 if(i*i!=sum)//如果不是sum的平方根 {factor[cnt++] = sum/i;//sum/i也是sum的因数 }}}sort(factor,factor+cnt);for(int i=cnt-1;i>=0;i--)//从大到小枚举,这样子第一个合法因数一定是最大的{if(check(factor[i]))//用来判断每个因数是否合法{cout<<factor[i];return 0;//别忘了return 0;}}return 0;
}相关文章:
小信砍柴的题解
目录 原题描述: 时间:1s 空间:256M 题目描述: 输入格式: 输出格式: 样例1输入: 题目大意: 主要思路: 注意事项: 总代码: 原题描述&#…...
华为OD机试 - 跳格子3(Java JS Python C)
题目描述 小明和朋友们一起玩跳格子游戏, 每个格子上有特定的分数 score = [1, -1, -6, 7, -17, 7], 从起点score[0]开始,每次最大的步长为k,请你返回小明跳到终点 score[n-1] 时,能得到的最大得分。 输入描述 第一行输入总的格子数量 n 第二行输入每个格子的分数 sc…...
每天五分钟计算机视觉:谷歌的Inception模块的计算成本的问题
计算成本 Inception 层还有一个问题,就是计算成本的问题,我们来看一下55 过滤器在该模块中的计算成本。 原始图片为28*28*192经过32个5*5的过滤操作,它的计算成本为: 我们输出28*28*32个数字,对于输出的每个数字来说,你都需要执行 55192 (5*5为卷积核的大小,192为通道…...
最新AI创作系统ChatGPT系统源码+DALL-E3文生图+支持AI绘画+GPT语音对话功能
一、AI创作系统 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美,可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI…...
78-C语言-完数的判断,以及输出其因子
简介:一个数如果恰好等于它的因子之和,这个数就称为完数,C语言编程找出1000之内的所有完数,并输出其因子。因子可以整除该数字的数, 如6的因子:1 2 3,6%10 6%20 6%30 解释全在注…...
C# 使用FluentHttpClient请求WebApi
写在前面 FluentHttpClient 是一个REST API 异步调用 HTTP 客户端,调用过程非常便捷,采用流式编程,可以将所有请求所需的参数一次性发送,并直接获取序列化后的结果。 老规矩从NuGet上安装该类库: 这边一定要认准是 P…...
AXure交互及案列
AXure交互及案列 1.交互样式简介2.axure交互事件简介3.axure交互动作简介4.axure情形简介2.完成案列1.登录案列2.省市联动案列3.左侧联动 1.交互样式简介 Axure是一种强大的原型设计工具,它允许用户创建高保真的交互式原型,用于演示和测试Web和移动应用…...
美颜SDK技术对比,深入了解视频美颜SDK的工作机制
如何在实时视频中呈现更加自然、美丽的画面,而这正是美颜SDK技术发挥作用的领域之一。本文将对几种主流视频美颜SDK进行深入比较,以揭示它们的工作机制及各自的优劣之处。 随着科技的不断进步,美颜技术已经从简单的图片处理发展到了视频领域…...
OkHttp ,使用 HttpUrl.Builder 来添加查询参数并添加到请求对象
在使用 OkHttp 中,你可以使用 HttpUrl.Builder 来添加查询参数并将其添加到请求对象中。下面是一个示例代码: import okhttp3.HttpUrl; import okhttp3.OkHttpClient; import okhttp3.Request; import okhttp3.Response;public class Main {public stat…...
图片速览 PoseGPT:基于量化的 3D 人体运动生成和预测(VQVAE)
papercodehttps://arxiv.org/pdf/2210.10542.pdfhttps://europe.naverlabs.com/research/computer-vision/posegpt/ 方法 将动作压缩到离散空间。使用GPT类的模型预测未来动作的离散索引。使用解码器解码动作得到输出。 效果 提出的方法在HumanAct12(一个标准但小规…...
Java对象结构
Java 对象(Object 实例)结构包括三部分:对象头、对象体、对齐字节。 Object的三个部分 对象头包括三个字段,第一个字段叫做 Mark Word(标记字),用于存储自身运行时的数据 例如 GC 标志位、哈希码、锁状态等信息。 第二个字段叫做 Class Pointer(类对象…...
基于redis的分布式锁实现方案
3. 基于redis的分布式锁实现方案: redis集群,原理是因为redis单线程串行处理. (1). SETNX方案: ①. SETNX(Set if not exists):a. 命令在指定的key不存在时,为key设置指定的值.b. SETNX Key Value设置成功,返回1.设置失败,返回0.c. 没有有效期的②. 原子操作(多个执行命令):Mu…...
基于JAVA+SpringBoot的线上智能问诊就医平台
✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目背景介绍: 智慧医药系统…...
adb: error: cannot create file/directory ‘d:/1.png‘: No such file or directory
将文件从设备读取到PC 由于权限问题,不能直接pull到电脑磁盘根目录,否则会报错: adb pull <remote> <local> eg: C:\Users\admin>adb pull /sdcard/server.log C:\Users\admin\Desktop /sdcard/server.log: 1 file pulled.…...
Pelee: A Real-Time Object Detection System on Mobile Devices(CVPR 2019)
文章目录 年三十AbstractIntroductionPeleeNet:一个高效的特征提取网络架构消融实验数据集不同设计选择对性能的影响 在ImageNet ILSVRC 2012上的结果真实设备上的速度 Pelee:实时目标检测系统Overview在VOC 2007上的结果不同设计选择的影响与其他框架的比较真实设备…...
分布式理论 | RPC | Spring Boot 整合 Dubbo + ZooKeeper
一、基础 分布式理论 什么是分布式系统? 在《分布式系统原理与范型》一书中有如下定义:“分布式系统是若干独立计算机的集合,这些计算机对于用户来说就像单个相关系统”; 分布式系统是由一组通过网络进行通信、为了完成共同的…...
局域网其他pc如何访问宿主机虚拟机IP?
文章目录 背景贝瑞蒲公英设置虚拟机网络连接测试 背景 使用贝瑞蒲公英异地组网,将家里的pc作为pgsql服务器在公司使用,但是虚拟机的ip和端口访问不了 贝瑞蒲公英 设置虚拟机网络 就是添加端口转发规则 连接测试 公网内其他pc连接测试 可以看到已经连接成…...
U8 语法制导翻译技术
文章目录 一、总述二、翻译文法1、概念 三、语法制导翻译1、概念2、带属性的翻译文法3)综合属性4)继承属性5)举例 3、 L-属性翻译文法(L-ATG)1)概念2)求值规则 4、简单赋值形式的L-ATGÿ…...
剑指offer A + B
剑指offer A B 题目 输入两个整数,求这两个整数的和是多少。 输入格式 输入两个整数A,B,用空格隔开,0≤A,B≤10的8次幂 输出格式 输出一个整数,表示这两个数的和 样例输入: 3 4样例输出: 7参考答…...
gitlab(gitlab-ce)下载,离线安装
目录 1.下载 2.安装 3.配置 4.启动 5.登录 参考: 1.下载 根据服务器操作系统版本,下载对应的RPM包。 gitlab官网: The DevSecOps Platform | GitLab rpm包官网下载地址: gitlab/gitlab-ce - Results in gitlab/gitlab-ce 国内镜像地…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
