当前位置: 首页 > news >正文

小信砍柴的题解

目录

原题描述:

时间:1s 空间:256M

题目描述:

输入格式:

输出格式:

样例1输入:

题目大意:

主要思路:

注意事项:

总代码:


原题描述:

时间:1s 空间:256M

题目描述:

小信家里有n段木材,初始长度表示为数组a。他可以进行以下填补操作至多m次(可以不操作):

选择两段木材i,j(i \ne j),将a_i长度截1补到a_j上,即操作后a_i = a_i-1,a_j = a_j+1

填补操作后,小信要将木材都砍成相同长度的小段,并且不能有剩余,请你告诉他最长的小段能有多长?

输入格式:

第一行包含两个整数n,m表示木材数和操作数。

第二行包含n个整数a_1,a_2,...,a_n,表示每段木材的初始长度。

输出格式:

输出一个整数,表示最长的小段的长度。

样例1输入:

2 1

15 9

样例1输出:

样例2输入:

2 10

15 9 

样例2输出:

24 

约定与提示:

对于100%的数据,2 \le n \le 500,1 \le a_i \le 10^6, 0 \le m \le10^9

样例1解释:选择i = 2,j=1操作之后序列变成[16,8],能切成3根长度为8的木材。

样例2解释:选择 i = 2,j=1操作9次之后序列变成[24,0],能切成1根长度为 24 的木材。

题目大意:

就是给你一个数组,然你可以操作最多m次,每次操作可以将一个数-1,另一个数+1,最后问你所有数的最大共约数(就是gcd)

主要思路:

直接上思维导图:

说一下几个重点,给上代码片段:

  1. 求因数:
    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的因数 }}
    }
  2. 将小的补给大的:
    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;
}

相关文章:

小信砍柴的题解

目录 原题描述&#xff1a; 时间&#xff1a;1s 空间&#xff1a;256M 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 样例1输入&#xff1a; 题目大意&#xff1a; 主要思路&#xff1a; 注意事项&#xff1a; 总代码&#xff1a; 原题描述&#…...

华为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绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如何搭建部署AI…...

78-C语言-完数的判断,以及输出其因子

简介&#xff1a;一个数如果恰好等于它的因子之和&#xff0c;这个数就称为完数&#xff0c;C语言编程找出1000之内的所有完数&#xff0c;并输出其因子。因子可以整除该数字的数&#xff0c; 如6的因子&#xff1a;1 2 3&#xff0c;6%10 6%20 6%30 解释全在注…...

C# 使用FluentHttpClient请求WebApi

写在前面 FluentHttpClient 是一个REST API 异步调用 HTTP 客户端&#xff0c;调用过程非常便捷&#xff0c;采用流式编程&#xff0c;可以将所有请求所需的参数一次性发送&#xff0c;并直接获取序列化后的结果。 老规矩从NuGet上安装该类库&#xff1a; 这边一定要认准是 P…...

AXure交互及案列

AXure交互及案列 1.交互样式简介2.axure交互事件简介3.axure交互动作简介4.axure情形简介2.完成案列1.登录案列2.省市联动案列3.左侧联动 1.交互样式简介 Axure是一种强大的原型设计工具&#xff0c;它允许用户创建高保真的交互式原型&#xff0c;用于演示和测试Web和移动应用…...

美颜SDK技术对比,深入了解视频美颜SDK的工作机制

如何在实时视频中呈现更加自然、美丽的画面&#xff0c;而这正是美颜SDK技术发挥作用的领域之一。本文将对几种主流视频美颜SDK进行深入比较&#xff0c;以揭示它们的工作机制及各自的优劣之处。 随着科技的不断进步&#xff0c;美颜技术已经从简单的图片处理发展到了视频领域…...

OkHttp ,使用 HttpUrl.Builder 来添加查询参数并添加到请求对象

在使用 OkHttp 中&#xff0c;你可以使用 HttpUrl.Builder 来添加查询参数并将其添加到请求对象中。下面是一个示例代码&#xff1a; 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&#xff08;一个标准但小规…...

Java对象结构

Java 对象(Object 实例)结构包括三部分:对象头、对象体、对齐字节。 Object的三个部分 对象头包括三个字段&#xff0c;第一个字段叫做 Mark Word(标记字)&#xff0c;用于存储自身运行时的数据 例如 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技术领域和毕业项目实战✌ &#x1f345;文末获取项目下载方式&#x1f345; 一、项目背景介绍&#xff1a; 智慧医药系统&#xf…...

adb: error: cannot create file/directory ‘d:/1.png‘: No such file or directory

将文件从设备读取到PC 由于权限问题&#xff0c;不能直接pull到电脑磁盘根目录&#xff0c;否则会报错&#xff1a; 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&#xff1a;一个高效的特征提取网络架构消融实验数据集不同设计选择对性能的影响 在ImageNet ILSVRC 2012上的结果真实设备上的速度 Pelee:实时目标检测系统Overview在VOC 2007上的结果不同设计选择的影响与其他框架的比较真实设备…...

分布式理论 | RPC | Spring Boot 整合 Dubbo + ZooKeeper

一、基础 分布式理论 什么是分布式系统&#xff1f; 在《分布式系统原理与范型》一书中有如下定义&#xff1a;“分布式系统是若干独立计算机的集合&#xff0c;这些计算机对于用户来说就像单个相关系统”&#xff1b; 分布式系统是由一组通过网络进行通信、为了完成共同的…...

局域网其他pc如何访问宿主机虚拟机IP?

文章目录 背景贝瑞蒲公英设置虚拟机网络连接测试 背景 使用贝瑞蒲公英异地组网&#xff0c;将家里的pc作为pgsql服务器在公司使用&#xff0c;但是虚拟机的ip和端口访问不了 贝瑞蒲公英 设置虚拟机网络 就是添加端口转发规则 连接测试 公网内其他pc连接测试 可以看到已经连接成…...

U8 语法制导翻译技术

文章目录 一、总述二、翻译文法1、概念 三、语法制导翻译1、概念2、带属性的翻译文法3&#xff09;综合属性4&#xff09;继承属性5&#xff09;举例 3、 L-属性翻译文法&#xff08;L-ATG&#xff09;1&#xff09;概念2&#xff09;求值规则 4、简单赋值形式的L-ATG&#xff…...

剑指offer A + B

剑指offer A B 题目 输入两个整数&#xff0c;求这两个整数的和是多少。 输入格式 输入两个整数A,B&#xff0c;用空格隔开&#xff0c;0≤A,B≤10的8次幂 输出格式 输出一个整数&#xff0c;表示这两个数的和 样例输入&#xff1a; 3 4样例输出&#xff1a; 7参考答…...

gitlab(gitlab-ce)下载,离线安装

目录 1.下载 2.安装 3.配置 4.启动 5.登录 参考&#xff1a; 1.下载 根据服务器操作系统版本&#xff0c;下载对应的RPM包。 gitlab官网&#xff1a; The DevSecOps Platform | GitLab rpm包官网下载地址: gitlab/gitlab-ce - Results in gitlab/gitlab-ce 国内镜像地…...

AI辅助架构设计:让快马平台智能规划trae状态管理方案

用AI辅助设计trae状态管理方案&#xff1a;以博客后台系统为例 最近在开发一个博客后台管理系统时&#xff0c;遇到了状态管理的难题。系统需要处理文章列表、编辑草稿、用户评论和系统设置等多种数据&#xff0c;如何合理组织这些状态让我头疼不已。幸运的是&#xff0c;在In…...

续航提升40%?EnergyStarX让Windows 11设备电量焦虑成为历史

续航提升40%&#xff1f;EnergyStarX让Windows 11设备电量焦虑成为历史 【免费下载链接】EnergyStarX &#x1f50b; Improve your Windows 11 devices battery life. A WinUI 3 GUI for https://github.com/imbushuo/EnergyStar. 项目地址: https://gitcode.com/gh_mirrors/…...

企业微信考勤自动化解决方案:基于EasyWeChat的实战指南

企业微信考勤自动化解决方案&#xff1a;基于EasyWeChat的实战指南 【免费下载链接】easywechat &#x1f4e6; 一个 PHP 微信 SDK 项目地址: https://gitcode.com/gh_mirrors/ea/easywechat 在数字化办公普及的今天&#xff0c;企业考勤管理面临着数据采集繁琐、统计分…...

告别重复造轮子:用快马AI一键生成openclaw项目高效串口调试工具

在机器人开发过程中&#xff0c;串口通信是最基础也最频繁使用的功能之一。无论是传感器数据采集、电机控制指令下发&#xff0c;还是与各种硬件模块的交互&#xff0c;都离不开串口通信的支持。然而每次新项目都要从头实现串口通信功能&#xff0c;不仅浪费时间&#xff0c;还…...

C语言学习笔记——2(数据类型,运算符)

数据类型机器中每个字节都有地址CPU通过地址访问字节空间#include <stdio.h>int main() {int a 0xEEAABAAA;printf("%#x, %d\n",a,a);unsigned int b 0xEEAABAAA;printf("%#x, %u\n",b,b);return 0; }运行结果&#xff1a;0xeeaabaaa, -290800982 …...

800元打造你的第一个自平衡机器人:Cubli Mini终极搭建指南

800元打造你的第一个自平衡机器人&#xff1a;Cubli Mini终极搭建指南 【免费下载链接】Cubli_Mini 项目地址: https://gitcode.com/gh_mirrors/cu/Cubli_Mini 想要亲手制作一个炫酷的自平衡机器人&#xff0c;但又担心成本太高、技术太难&#xff1f;Cubli Mini正是为…...

TP-Link Linux驱动开发面试全记录与实战技巧

1. TP-Link软件工程师面试全记录&#xff1a;Linux驱动开发方向作为一名在嵌入式Linux领域摸爬滚打多年的工程师&#xff0c;最近参加了TP-Link的软件工程师面试&#xff0c;岗位方向是Linux驱动开发。说实话&#xff0c;去之前我对TP-Link的认知还停留在"路由器方案商&qu…...

RK3568 Serdes方案调试:基于THCV244的I2C透传与MIPI CSI链路配置

1. RK3568与THCV244 Serdes方案概述 在车载摄像头和工业视觉应用中&#xff0c;Serdes&#xff08;串行器/解串器&#xff09;技术正变得越来越重要。RK3568作为一款高性能处理器&#xff0c;配合THCV244 Serdes芯片&#xff0c;能够实现远距离传感器数据的稳定传输。这套方案的…...

AI 模型推理 GPU 调度性能分析

AI模型推理GPU调度性能分析&#xff1a;解锁算力潜能的关键 随着AI技术的快速发展&#xff0c;深度学习模型的推理任务对计算资源的需求急剧增加。GPU因其并行计算能力成为模型推理的核心硬件&#xff0c;但如何高效调度GPU资源以提升性能&#xff0c;成为企业和研究机构关注的…...

从零到开张:在本地虚拟机搭建yshop-drink点餐系统,模拟真实小店运营环境

从零到开张&#xff1a;在本地虚拟机搭建yshop-drink点餐系统&#xff0c;模拟真实小店运营环境 想象一下&#xff0c;你刚租下一间临街小铺&#xff0c;准备开一家奶茶店。装修完毕&#xff0c;设备到位&#xff0c;现在只差一个能让顾客自助下单的点餐系统。市面上的SaaS服务…...