[C++知识库]题目 2305: 蓝桥杯2019年第十届省赛真题-等差数列

题目

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

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

输入
输入的第一行包含一个整数 N。 第二行包含N个整数A1,A2,···,AN。(注意A1 ～AN并不一定是按等差数列中的顺序给出)

(对于所有评测用例，2≤ N ≤100000，0≤ Ai ≤109。)

输出
输出一个整数表示答案

样例输入

5
2 6 4 10 20

样例输出

10

解题思路

将读入的数据从小到大排序，最小的相邻两个数之差（大减小，差一定为正）即为公差，之后用等差数列的公式：

项数 = (An-A1)/公差+1

即可求得该数列至少有多少项。

易错点

注意公差为0的也被认为是等差数列，因此当所有输入数字一致时，该等差数列最少的项数等于输入数据数。

代码

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a, const void *b){
    return *(int *)a - *(int *)b;//升序
}

int main()
{
	int N,i,diff=1000000000,num;
	scanf("%d",&N);
	int a[N];
	for (i=0;i<N;i++)
	    scanf("%d",&a[i]);
	qsort(a,N,sizeof(int),cmp);
	for (i=1;i<N;i++)
	    if ((a[i]-a[i-1])<diff)
	        diff = a[i]-a[i-1];//公差
	if (diff==0)
	    num = N;
	else
	    num = (a[N-1]-a[0])/diff+1;
	printf("%d",num);
	return 0;
}