【蓝桥杯】历届真题 等差数列(省赛)Java

article/2024/4/19 23:28:41

【资源限制】

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

【问题描述】

        数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N个整数。

        现在给出这N个整数,小明想知道包含这N个整数的最短的等差数列有几项?

【输入格式】

        输入的第一行包含一个整数N。

        第二行包含N个整数A1,A2,.… ,AN。(注意Ai~Ax并不一定是按等差数列中的顺序给出)

【输出格式】

        输出一个整数表示答案。

【样例输入】

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≤A; ≤ 10^9。

【思路与分析】

        求最大的等差数列,说白了也就是求最大数和最小数之间的最大公约数。根据题意已知:所给元素顺序并不一定是按等差数列中的顺序给出。因此,最先进行的操作是对于获取的数组元素进行排序。

        而后根据等差数列的求和公式(an=a1+(n-1)*d)的变式(n= (an-a1)/d+1)进行计算。

【代码】

/*
输入的第一行包含一个整数N。
第二行包含N个整数A1,A2,…  ,AN。
(注意Ai~Ax并不一定是按等差数列中的顺序给出)
*/
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int[] arr=new int[n];for(int i=0;i<n;i++){arr[i]=sc.nextInt();}Arrays.sort(arr);int m=0;for(int i=0;i<arr.length-1;i++){m=temp(m,arr[i+1]-arr[i]);}//项数为0直接输出公约数if(m==0){System.out.println(n);} else {long num=0;System.out.println((arr[n-1]-arr[0])/m+1);}}//利用三元运算求两个正整数的最大公约数public static int temp(int a,int b){return b!=0?temp(b,a%b):a;}
}


http://www.ngui.cc/article/show-861332.html

相关文章

我对架构师的理解

何为架构师 架构师在我看来只是一个头衔。 因为软件架构发生在做每一个功能模块的时候&#xff0c;需要需求分析和设计&#xff0c;技术选型&#xff0c;估时&#xff0c;工作分配&#xff0c;开发&#xff0c;安全校验&#xff0c;日志监控。 这期间还会涉及到各种部门内部…

swagger2接口文档

文章目录简介Open APISwagger简介Spring-fox入门案例第一步&#xff1a;导入依赖第二步&#xff1a;编写controller类第三步&#xff1a;编写启动类第四步&#xff1a;运行启动类并访问ui页面Swagger UI 介绍基础信息配置自定义注解&#xff08;防止有些类不生成接口文档&#…

日常练习:C++编程题

1.数对 纯数学,推公式 2.除自身数组以外的乘积 数组before记录每个数字之前的积数组end记录每个数字之后的积 3.圣诞树 这道题的特殊情况不好解决&#xff0c;用了个int m n&#xff0c;后面用m--控制特殊情况的个数 4.超级圣诞树 有一点难 5.回型矩阵 a[i][j], …

前端面试记录(一)

面试时间&#xff1a;2023年2月3日14:00 前端实习 感想&#xff1a;第一次面试&#xff0c;没想到就面了个大厂&#xff08;非头部大厂&#xff09;&#xff0c;0面试经验也非常紧张&#xff0c;看了一上午面经也没记住多少东西。其实问的问题非常简单&#xff0c;但是计算…

高码率QPSK调制解调方案(2.1 QPSK调制)

2 全数字高码率QPSK调制解调软件设计 2.1 QPSK调制 2.1.1 QPSK调制原理 QPSK调制即正交相移键控信号,其信号表达式为 (1) 其中,和分别表示每比特的能量和持续

第6章 Linux 系统目录结构教程

Linux 系统目录结构 登录系统后&#xff0c;在当前命令窗口下输入命令&#xff1a; ls / 帅哥您会看到树状目录结构 以下是对这些目录的解释&#xff1a; /bin&#xff1a; bin 是 Binaries (二进制文件) 的缩写, 这个目录存放着最经常使用的命令。 /boot&#xff1a; 这里存…

上市条件 - 打造企业上市系列文章

一、只有股份公司才具备上市的资格; 二、申请上市公司&#xff0c;公司经营必须是3年以上&#xff0c;在这三年内没有更换过董事、高层管理人员、并且公司经营合法、符合国家法律规定; 三、上市公司的注册资金无虚假出资&#xff0c;没有抽逃资金的现象; 四、上市公司的注册资金…

03俯瞰全局:gRPC是如何进行通信的

gRPC作为Web网站和APP后端的最常用服务提供方式之一和分布式微服务架构不同节点间的最常见通信方式之一,它自身是如何进行通信的呢,这个问题就是我们本篇文章将要研究的重点,先从全局的角度分析gRPC服务端和客户端进行通信的主要流程,再从细节剖析gRPC是如何进行高效的远程…

Kafka入门(一)

1、Kafka简介 Kafka是一个分布式的基于发布/订阅模式的消息队列&#xff08;Message Queue&#xff09;&#xff0c;主要应用于大数据实时处理领域&#xff08;hadoop集群&#xff09;、物联网领域。其主要设计目标如下&#xff1a; 以时间复杂度为O(1)的方式提供消息持久化能…

【实际开发12】- 经验 experience

目录 1. 经验 experience 1. 无多大价值 , 停留数据展示层面 2. 保证数据一致性问题 3. 新增时 , 可先关注核心基础数据 ( 复杂数据以修改形式完善 ) 4. 新增 / 修改 ( 幂等性处理 ) 5. 增 / 删 / 改 添加日志 , 查询无需日志 6. 需要对接多模块的通用字段设计 : String…