第十届省赛——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)引入狙击手、森林老人和…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...

Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...