【蓝桥杯】等差数列

【蓝桥杯】等差数列 等差数列

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

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

输入描述
输入的第一行包含一个整数 N。
第二行包含 N 个整数，不一定按照等差数列的顺序给出

数据范围
2 <= N <=105
0 <= Ai <=109

输出描述
输出一个整数表示答案。

输入输出样例
示例
输入

5
2 6 4 10 20

输出

10

思路：先从小到大排序，然后找出两个元素之间的最小间距，作为公差，若公差不为0则套用公式 项 数 = ( 末 项 − 首 项 ) / 公 差 + 1 项数=(末项-首项)/公差+1 项数=(末项−首项)/公差+1即可求出项数若公差为0，则要求数列中所有数都一样，因为从小到大排了序，故只需判断数列最后一项是否与第一项相同即可，若相同，则输出n，若不相同则说明不符合题意，我在代码中用0表示(但实际上如果题的数据均合法是不会用到的，加上不会影响并且使情况更加全面) 代码如下

#include 
#include 
#include 
using namespace std;
int n;
vector arr;
int main(void) {
    scanf("%d", &n);
    arr.resize(n, 0);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    sort(arr.begin(), arr.end());
    int tmp = arr[1] - arr[0];
    for (int i = 2; i < n; i++) {
        tmp = min(tmp, arr[i] - arr[i - 1]);
    }
    printf("%dn", tmp == 0?((arr[n - 1] == arr[0]) ? n : 0):((arr[n - 1] - arr[0]) / tmp + 1));
    return 0;
}