第十届省赛——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)引入狙击手、森林老人和…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
