【洛谷 P8682】[蓝桥杯 2019 省 B] 等差数列 题解（数学+排序+差分）

[蓝桥杯 2019 省 B] 等差数列

题目描述

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

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

输入格式

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

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

输出格式

输出一个整数表示答案。

样例 #1

样例输入 #1

5
2 6 4 10 20
1
2

样例输出 #1

10
1

提示

包含 2,6,4,10,20 的最短的等差数列是 2,4,6,8,10,12,14,16,18,20。

对于所有评测用例，$2\le N\le 10^5$，$0\le A_i\le 10^9$。

蓝桥杯 2019 年省赛 B 组 H 题。

---

思路

首先，定义一些常量和变量。N 是一个整数常量，用来表示数组的最大长度。INF 是一个无穷大的常量，用于初始化最小差值。n 是一个整数，表示输入的整数数量。a[N] 和 diff[N] 是两个整数数组，分别用来存储输入的整数和相邻整数的差值。

接着，从标准输入读取整数数量 n 和 n 个整数，存入数组 a。将数组 a 进行排序，这样可以将给定的整数按照自然顺序排列。然后，计算并存储数组 a 中相邻整数的差值，同时更新最小差值 dmin。

最后，如果最小差值 dmin 不为零，则输出 (a[n] - a[1]) / dmin + 1，这是等差数列的项数公式，表示包含这 n 个整数的最短等差数列的项数。如果最小差值 dmin 为零，说明所有给定的整数都相同，那么输出 n，表示最短等差数列的项数就是给定的整数数量。

注意

需要进行特判，当公差为0时，所有数都相同，直接输出n，否则会引发除零异常。

---

AC代码

#include 
#include 
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int n;
int a[N];
int diff[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	int dmin = INF;
	sort(a + 1, a + n + 1);
	for (int i = 2; i <= n; i++) {
		diff[i] = a[i] - a[i - 1];
		dmin = min(dmin, diff[i]);
	}
	cout << (dmin ? ((a[n] - a[1]) / dmin + 1) : n) << "\n";
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35