第十届省赛——9等差数列(集合做法)
题目:
试题 I: 等差数列
时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分
【问题描述】
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一
部分的数列,只记得其中 N 个整数。
现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有
几项?
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN。(注意 A1 ∼ AN 并不一定是按等差数
列中的顺序给出)
【输出格式】
输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】
10
【样例说明】
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、
18、20。
【评测用例规模与约定】
对于所有评测用例,2 ≤ N ≤ 100000,0 ≤ Ai ≤ 109。
分析:
先用集合储存这串数字,然后自然排序从小到大。首先我们先找到公差,公差最大为这个数列的第二项减第一项,先从最大的可能性公差进行判断,如果不对就减一,在进行公差的判断。
公差的判断方法是,从第二项开始减去前一项,只要能被d整除,一直能够除到最后还是能被整除,那么就这是公差
找到公差之后我们让最大一项减去第一项除以公差加一,就是最短等差数列的长度。
如下图是测试的多种可能性



步骤:

package 历届真题省赛阶段;import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;public class 测试1 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();ArrayList<Integer> arrayList = new ArrayList<>();for (int i = 0; i < n; i++) {arrayList.add(sc.nextInt());}Collections.sort(arrayList);int d = arrayList.get(1)-arrayList.get(0);for (int i = 0;; i++) {Boolean pan = f(d - i, arrayList, n);// 求是不是公差if (pan) {d = d - i;break;}}System.out.println((arrayList.get(n-1)-arrayList.get(0)) / d + 1);sc.close();}private static Boolean f(int d, ArrayList<Integer> arrayList, int n) {for (int i = 1; i < n; i++) {int cha = arrayList.get(i)-arrayList.get(i-1);if (cha % d == 0) {continue;} else {return false;}}return true;}}
相关文章:

第十届省赛——9等差数列(集合做法)
题目:试题 I: 等差数列时间限制: 1.0s 内存限制: 512.0MB 本题总分:25 分【问题描述】数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中 N 个整数。现在给出这 N 个整数,小明想知道包含这…...

《数据分析-JiMuReport03》JiMuReport报表设计入门介绍-新建报表
报表设计 1 新建报表 1.1 创建新的数据报表 以数据报表为例,简单介绍创建报表的过程 1.2 进入报表设计页面 如下图可见,主要分为四个模块: 模块一(左) 数据集管理报表信息数据字典 模块二(右) 这部分是对数据报表的进一步优化 模块三(上…...

从功能测试进阶自动化测试,爆肝7天整理出这一份超全学习指南【附网盘资源】
因为我最近在分享自动化测试技术,经常被问到:功能测试想转自动化,请问应该怎么入手?有没有好的资源推荐?那么,接下来我就结合自己的经历聊一聊我是如何在工作中做自动化测试的。(学习路线和网盘…...

CNN神经网络——手写体识别
目录 Load The Datesets Defining,Training,Measuring CNN Algorithm Datasets GRAET HONOR TO SHARE MY KNOWLEDGE WITH YOU This paper is going to show how to use keras to relize a CNN model for digits classfication Load The Datesets The datasets files are …...

python调试模块ipdb
1. 调试python ipdb是用来python中用以交互式debug的模块,可以直接利用pip安装; 其功能类似于pycharm中 python控制台, 而使用ipdb 的优点,便是直接在代码中调试, 避免了在python控制台,或者重新设置一些简单变量。…...

【数据库】聊聊MySQL的日志,binlog、undo log、redo log
日志 在数据库中,如何保证数据的回滚,以及数据同步,系统宕机后可以恢复到原来的状态,其实就是依靠日志。 其中bin log是Server层特有的,redo log是Innodb存储引擎特有的。 bin log 是逻辑日志,主要记录这条…...

aws dynamodb java低等级api和高级客户端api的使用
参考资料 https://docs.amazonaws.cn/zh_cn/sdk-for-java/latest/developer-guide/setup-project-maven.html 初始化环境 创建maven项目 mvn org.apache.maven.plugins:maven-archetype-plugin:3.1.2:generate \-DarchetypeArtifactId"maven-archetype-quickstart&quo…...

Kafka中那些巧妙的设计
一、kafka的架构 Kafka是一个分布式、多分区、基于发布/订阅模式的消息队列(Message Queue),具有可扩展和高吞吐率的特点。 kafka中大致包含以下部分: Producer: 消息生产者,向 Kafka Broker 发消息的客户…...

《JavaEE》进程和线程的区别和联系
👑作者主页:Java冰激凌 📖专栏链接:JavaEE 目录 进程是什么? 线程是什么? 进程和线程之间的联系~ ps1:假设我们当前的大兴国际机场有一条登机口可以登入飞机 ps2:我们为…...

Matlab生成sinc信号
Matlab生成sinc信号 在Matlab中生成sinc信号非常容易。首先,我们需要了解什么是sinc波形。 sinc波形是一种理想的信号,它在时域上是一个宽度为无穷的矩形函数,而在频域上则是一个平的频谱。它的公式为: sinc(x)sin(πx)πx\…...

进程与线程区别与联系
进程与线程的区别与联系线程线程介绍为什么要有线程呢?线程与进程的区别于联系(重点)线程 线程介绍 我们知道进程就是运行起来的程序, 那线程又是什么呢? 一个线程就是一个 “执行流”. 每个线程之间都可以按照顺序执行自己的代码. 多个线程之间 “同时” 执行着多份代码. …...

使用vbscript.regexp实现VBA代码格式化
Office自带的VBE在编辑代码时,没有自动完成代码缩进的功能,而我们在网上找到的VBA代码,经常没有实现良好的自动缩进,复制到VBE后,可读性较差。本文介绍的宏,通过使用vbscript.regexp对象,利用正…...

选择结构习题:百分值转换成其相应的等级
Description 编一程序,输入一个百分制的成绩(整数类型),按要求输出相应的字符串信息,对应关系为: excellent 90-100 good 80-89 middle 70-79 pass 60-69 fail 60以下或100以上 Input 输入仅一行&…...

c# 源生成器
本文概述了 .NET Compiler Platform(“Roslyn”)SDK 附带的源生成器。 通过源生成器,C# 开发人员可以在编译用户代码时检查用户代码。 生成器可以动态创建新的 C# 源文件,这些文件将添加到用户的编译中。 这样,代码可以…...

[N1CTF 2018]eating_cms1
一个cms,先打开环境试了一下弱口令,无效,再试一下万能密码,告诉我有waf,先不想怎么绕过,直接开扫(信息收集)访问register.php注册一个账号进行登录上面的链接尝试用php读文件http://…...

数据结构与算法基础(王卓)(15):KMP算法详解(含速成套路和详细思路剖析)
如果时间不够,急(忙)着应付考试没心思看,直接参考(照抄)如下套路: PART 1:关于next [ j ] PPT:P30 根据书上以及视频上给出的思路(提醒)&#x…...

【互联网架构】聊一聊所谓的“跨语言、跨平台“
文章目录序跨语言跨平台【饭后杂谈】为什么有人说Java的跨平台很鸡肋?序 很多技术都具有跨语言、跨平台的特点 比如JSON是跨语言的、Java是跨平台的、UniAPP、Electron是跨平台的 跨语言和跨平台,是比较重要的一个特性。这些特性经常能够决定开发者是否…...

1.JVM常识之 类加载器
1.jvm组成 JVM组成: 1.类加载器 2.运行时数据区 3.执行引擎 4.本地库接口 各组件的作用: 首先通过类加载器(ClassLoader)会把 Java 代码转换成字节码,运行时数据区(Runtime Data Area)再把字节码…...

一天搞定《AI工程师的PySide2 PyQt5实战开发手册》
PySide2/PySide6、PyQt5/PyQt6:都是基于Qt 的Python库,可以形象地这样说,PySide2 是Qt的 亲儿子(Qt官方开发的) , PyQt5 是Qt还没有亲儿子之前的收的 义子 (Riverbank Computing这个公司开发的,有商业版权限…...

身份推理桌游
目录 杀人游戏(天黑请闭眼) (1)入门版 (2)标准版 (3)延伸版——百度百科 (3.1)引入医生和秘密警察 (3.2)引入狙击手、森林老人和…...

[LeetCode周赛复盘] 第 99 场双周赛20230304
[LeetCode周赛复盘] 第 99 场双周赛20230304 一、本周周赛总结二、 [Easy] 2578. 最小和分割1. 题目描述2. 思路分析3. 代码实现三、[Medium] 2579. 统计染色格子数1. 题目描述2. 思路分析3. 代码实现四、[Medium] 2580. 统计将重叠区间合并成组的方案数1. 题目描述2. 思路分析…...

Parcel Bundle漏洞学习
Bundle的序列化细节看上去还是有些复杂的,在之前已经讨论过,一般我们使用Parcel的时候,都是严格的write和read相对应。一些疏漏,不对应,竟然就可以成为漏洞,https://xz.aliyun.com/t/2364 里介绍了Bundle漏…...

RTP载荷H264(实战细节)
RTP包由两部分组成,RTP头和RTP载荷: RTP头 RTP头的 结构如下: 代码结构: typedef struct RtpHdr {uint8_t cc : 4, // CSRC countx : 1, // header extendp : 1, // padding flagversion : 2; // versionuint8_t …...

软考高级信息系统项目管理师系列之四十三:信息系统安全管理
软考高级信息系统项目管理师系列之四十三:信息系统安全管理 一、信息系统安全管理内容二、信息安全策略1.信息系统安全策略的概念与内容2.信息系统安全等级保护的概念三、信息安全系统1.信息安全系统三维空间2.信息安全系统三种架构体系四、PKI公开密钥基础设施1.PKI总体架构2…...

并发编程之AtomicUnsafe
目录 原子操作 定义 术语 处理器如何实现原子操作 处理器自动保证基本内存操作的原子性 使用总线锁保证原子性 使用缓存锁保证原子性 Java当中如何实现原子操作 Atomic 定义 原子更新基本类型类 原子更新数组类 原子更新引用类型 原子更新字段类 Unsafe应用解析…...

GDB调试快速入门
什么是GDB: GDB - - - (GNU symbolic debugger)是Linux平台下最常用的一款程序调试器。 自己的Linux是否安装GDB? 一般来说,使用Ubuntu的话,系统就会自带的有GDB调试器的 命令窗口输入如下命令可以查看是否安装了gdb: gdb -v …...

Vim一次复制,多次粘贴
我们平常在使用Vim时候,通过viwy或者yy等复制操作之后,p操作粘贴的时候,只能粘贴一次,想要粘贴多次怎么办? 解决方案:在使用p的是时候使用"0p,这样就能无限制的一直粘贴了。 可是ÿ…...

如何修改Win11上的默认程序?
在Win10之前,更改特定文件格式的默认程序很简单,但在Win11发布之后,很多用户都不清楚关于Win11的修改默认程序的操作步骤,接下来我们就一起来看看吧,希望可以帮助到大家。 步骤如下: 一、如何更改Windows 1…...

安装Linux虚拟机和Hadoop平台教程汇总及踩坑总结
📍主要内容介绍安装Linux虚拟机、ubuntu系统、安装hadoop三个环节的教程链接介绍及本机与虚拟机的FTP传输教程总结(直接找hadoop安装环节的5.filezilla传输文件)新鲜出炉的踩坑总结和填坑指南安装Linux虚拟机和ubuntu系统一、材料和工具1、下…...

Shell脚本的使用和介绍
为了方便以后工作使用和复习,吐血整理记录一下学习shell脚本的笔记,看这篇文章需要对linux系统熟悉,希望对大家有所帮助! 文章目录 目录 文章目录 一、什么是shell? 为什么要学习和使用shell? 二、shell的分类...