小信砍柴的题解
目录
原题描述:
时间: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 国内镜像地…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
