小信砍柴的题解
目录
原题描述:
时间: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 国内镜像地…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
