【洛谷 P8682】[蓝桥杯 2019 省 B] 等差数列 题解(数学+排序+辗转相除法)
[蓝桥杯 2019 省 B] 等差数列
题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中 N N N 个整数。
现在给出这 N N N 个整数,小明想知道包含这 N N N 个整数的最短的等差数列有几项?
输入格式
输入的第一行包含一个整数 N N N。
第二行包含 N N N 个整数 A 1 , A 2 , ⋯ , A N A_1,A_2,\cdots,A_N A1,A2,⋯,AN。(注意 A 1 ∼ A N A_1 ∼ A_N A1∼AN 并不一定是按等差数列中的顺序给出 )。
输出格式
输出一个整数表示答案。
样例 #1
样例输入 #1
5
2 6 4 10 20
样例输出 #1
10
提示
包含 2,6,4,10,20 的最短的等差数列是 2,4,6,8,10,12,14,16,18,20。
对于所有评测用例, 2 ≤ N ≤ 1 0 5 2 \le N \le 10^5 2≤N≤105, 0 ≤ A i ≤ 1 0 9 0 \le A_i \le 10^9 0≤Ai≤109。
蓝桥杯 2019 年省赛 B 组 H 题。
思路
首先,定义一些常量和变量,包括数组大小N,数组a,还有一个使用辗转相除法计算两数最大公约数的函数gcd。
接着,从输入中读取了一个整数n,然后读取了n个整数并存储在数组a中。定义了一个整数d,用来存储数组a中第二个元素和第一个元素的差值。然后对数组a进行了排序。
接下来,遍历数组a,从第三个元素开始,计算每个元素和前一个元素的差值,然后用gcd函数求出这个差值和d的最大公约数,并将结果赋值给d。
最后,如果d不为0,输出((a[n] - a[1]) / d + 1),否则输出n。
注意
需要进行特判,当公差为0时,所有数都相同,直接输出n,否则会引发除零异常。

AC代码
#include <algorithm>
#include <iostream>
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;
int a[N];
int diff[N];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}int dmin = INF;sort(a + 1, a + n + 1);for (int i = 2; i <= n; i++) {diff[i] = a[i] - a[i - 1];dmin = min(dmin, diff[i]);}cout << (dmin ? ((a[n] - a[1]) / dmin + 1) : n) << "\n";return 0;
}相关文章:
【洛谷 P8682】[蓝桥杯 2019 省 B] 等差数列 题解(数学+排序+辗转相除法)
[蓝桥杯 2019 省 B] 等差数列 题目描述 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中 N N N 个整数。 现在给出这 N N N 个整数,小明想知道包含这 N N N 个整数的最短的等差数列有几项? 输…...
Linux:kubernetes(k8s)部署CNI网络插件(4)
在上一章进行了node加入master Linux:kubernetes(k8s)node节点加入master主节点(3)-CSDN博客https://blog.csdn.net/w14768855/article/details/136420447?spm1001.2014.3001.5501 但是他们显示还是没准备好 看一下…...
docker save 命令 docker load 命令 快速复制容器
docker save 命令 docker load 命令 1、docker save 命令2、docker load 命令 1、docker save 命令 docker save 命令用于在系统上把正在使用的某个容器镜像 导出成容器镜像文件保存下载,以便在其他系统上导入这个容器镜像文件 以便快速在其他服务器上启动相同的容…...
Apache Flink连载(三十七):Flink基于Kubernetes部署(7)-Kubernetes 集群搭建-3
🏡 个人主页:IT贫道-CSDN博客 🚩 私聊博主:私聊博主加WX好友,获取更多资料哦~ 🔔 博主个人B栈地址:豹哥教你学编程的个人空间-豹哥教你学编程个人主页-哔哩哔哩视频 目录...
【机器学习】实验6,基于集成学习的 Amazon 用户评论质量预测
清华大学驭风计划课程链接 学堂在线 - 精品在线课程学习平台 (xuetangx.com) 代码和报告均为本人自己实现(实验满分),此次代码开源大家可以自行参考学习 有任何疑问或者问题,也欢迎私信博主,大家可以相互讨论交流哟…...
【寸铁的刷题笔记】图论、bfs、dfs
【寸铁的刷题笔记】图论、bfs、dfs 大家好 我是寸铁👊 金三银四,图论基础结合bfs、dfs是必考的知识点✨ 快跟着寸铁刷起来!面试顺利上岸👋 喜欢的小伙伴可以点点关注 💝 🌞详见如下专栏🌞 &…...
vue2 + axios + mock.js封装过程,包含mock.js获取数据时报404状态的解决记录,带图文,超详细!!!
vue axios mock.js 以下是封装的过程,记录一下 1、首先先了解什么是mock.js的用途及特点 官网地址:Mock.js (mockjs.com) 作用:生成随机数据,拦截 Ajax 请求 优势: 2、了解axios的原理及使用 官网地址:…...
对象变更记录objectlog工具(持续跟新)
文章目录 前言演示代码演示环境引入项目项目框架操作步骤 设计介绍参考仓库 前言 系统基于mybatis-plus, springboot环境 对于重要的一些数据,我们需要记录一条记录的所有版本变化过程,做到持续追踪,为后续问题追踪提供思路。下面展示预期效果…...
平衡二叉树,二叉树的路径,左叶子之和
第六章 二叉树part04 今日内容: 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之和 110.平衡二叉树 (优先掌握递归) 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为&am…...
Sodinokibi勒索病毒最新变种,解密工具更新到2.0版本
Sodinokibi勒索病毒 Sodinokibi勒索病毒又称REvil,自从2019年6月1日,GandCrab勒索病毒运营团伙宣布停止运营之后,Sodinokibi勒索病毒马上接管了GandCrab的大部分传播渠道,同时它也被称为是GandCrab勒索病毒的“接班人”ÿ…...
css 鼠标移入放大的效果
效果 HTML <div class"img-wrap"><img class"img-item" src"../assets/1.png" alt"" srcset""></div> CSS <style lang"less" scoped> .img-wrap {/* 超出隐藏 */overflow: hidden;.img-…...
Transformer模型分布式并行通信量浅析
1.数据并行DP(朴素数据并行,Zero数据并行之后补充) O ( h 2 ∗ l ) O(h^2*l) O(h2∗l) 每台机器做完自己的梯度后需要做一次All reduce操作来累积梯度,故一个batch计算发送的数据量为每层梯度大小 h 2 h^2 h2乘以层数 l l l 优点…...
PMP考试之20240304
1.一家食品公司正在使用预测型方法开发一种新产品,该产品目前正处于测试阶段。鉴于测试反馈的性质,项目经理决定使用迭代方法。在其中一个迭代结束时,颁布了与该产品有关的新法规。项目经理接下来应该做什么? A.就项目的范围提出…...
智慧城市中的公共服务创新:让城市生活更便捷
目录 一、引言 二、智慧城市公共服务创新的实践 1、智慧交通系统 2、智慧医疗服务 3、智慧教育系统 4、智慧能源管理 三、智慧城市公共服务创新的挑战 四、智慧城市公共服务创新的前景 五、结论 一、引言 随着信息技术的迅猛发展,智慧城市已成为现代城市发…...
bert 相似度任务训练完整版
任务 之前写了一个相似度任务的版本:bert 相似度任务训练简单版本,faiss 寻找相似 topk-CSDN博客 相似度用的是 0,1,相当于分类任务,现在我们相似度有评分,不再是 0,1 了,分数为 0-5,数字越大…...
Ribbon实现Cloud负载均衡
安装Zookeeper要先安装JDK环境 解压 tar -zxvf /usr/local/develop/jdk-8u191-linux-x64.tar.gz -C /usr/local/develop 配置JAVA_HOME vim /etc/profile export JAVA_HOME/usr/local/develop/jdk1.8.0_191 export PATH$JAVA_HOME/bin:$PATH export CLASSPATH.:$JAVA_HOM…...
【UE 材质】制作加载图案(2)
在上一篇(【UE 材质】制作加载图案)基础上继续实现如下效果的加载图案 效果 步骤 1. 复制一份上一篇制作的材质并打开 2. 添加“Floor”节点向下取整 除相同的平铺数 此时的效果如下 删除如下节点 通过“Ceil”向上取整,参数“Tiling”默认…...
为啥要用C艹不用C?
在很多时候,有人会有这样的疑问 ——为什么要用C?C相对于C优势是什么? 最近两年一直在做Linux应用,能明显的感受到C带来到帮助以及快感 之前,我在文章里面提到环形队列 C语言,环形队列 环形队列到底是怎么回…...
Java:JVM基础
文章目录 参考JVM内存区域程序计数器虚拟机栈本地方法栈堆方法区符号引用与直接引用运行时常量池字符串常量池直接内存 参考 JavaGuide JVM内存区域 程序计数器 程序计数器是一块较小的内存空间,可以看做是当前线程所执行的字节码的行号指示器,各线程…...
JavaSec 基础之五大不安全组件
文章目录 不安全组件(框架)-Shiro&FastJson&Jackson&XStream&Log4jLog4jShiroJacksonFastJsonXStream 不安全组件(框架)-Shiro&FastJson&Jackson&XStream&Log4j Log4j Apache的一个开源项目,是一个基于Java的日志记录框架。 历史…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...
