【排序, 枚举】等差数列【蓝桥杯】

题目

等差数列 - 蓝桥云课

---

题目描述

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

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

输入描述

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

第二行包含 $N$ 个整数 $A_1,A_2,··· ,A_N$。(注意 $A_1 \sim A_N$ 并不一定是按等差数列中的顺序给出)

其中，$2 \leq N \leq 10^5，0 \leq A_i \leq 10^9$。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

5
2 6 4 10 20

输出

10

样例说明： 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解题

方法一：排序 枚举

思路

读入数列排序后遍历，两两作差求出一个最小差(mn)，如果 mn 不为零则等差数列最短有 $\frac{A_N - A_1}{mn} + 1$ 项。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        Arrays.sort(a);
        int mn = a[n - 1] - a[0];
        for (int i = 1; i < n; ++i) {
            mn = Math.min(mn, a[i] - a[i - 1]);
        }
        System.out.println(mn == 0 ? n : (a[n - 1] - a[0]) / mn + 1);
    }
}