[数据结构与算法]第十届蓝桥杯B组省赛-等差数列

题目

题目链接

题解

数论。

先规定输入数列经从小到大排序后为：

$A_1$、 $A_2$、$A_3$、$...$、$A_{n?1}$、$A_n$

规定 { A i } \{A_i\} {Ai?} 数列所在的原数列为公比为 $d$ 的 { a i } \{a_i\} {ai?} ， { a i } \{a_i\} {ai?} 表示为：
$a_1$、$a_2$、$a_3$、$...$、$a_{t?1}$、$a_t$、$...$

因为 { A i } \{A_i\} {Ai?} 为 { a i } \{a_i\} {ai?} 的子数列，所以 { A i } \{A_i\} {Ai?} 中的每个元素也一定满足 { a i } \{a_i\} {ai?} 的通项公式：

$A_1=a_1+(k_1?1)?d$
$A_2=a_1+(k_2?1)?d$
$...$
$A_{n?1}=a_1+(k_{n?1}?1)?d$
$A_n=a_1+(k_n?1)?d$

其中，正如等差数列通项公式 $b_n=b_1+(n?1)?d$一样，$k_i$ 的含义与通项公式中的 $n$ 相同，表示的是 $A_i$ 在原数列 { a i } \{a_i\} {ai?} 中排在第几个（从$1$开始）

计算 { A i } \{A_i\} {Ai?} 相邻的两个元素的差值：

$dif{f}_1=A_2?A_1=(k_2?k_1)?d$
$dif{f}_2=A_3?A_2=(k_3?k_2)?d$
$...$
$dif{f}_{n?1}=A_n?A_{n?1}=(k_n?k_{n?1})?d$

因为 $k_i?k_{i?1}$ 是整数，所以存在如下要求：

$dif{f}_1\%d=0$
$dif{f}_2\%d=0$
$...$
$dif{f}_{n?1}\%d=0$

即要求任意 $dif{f}_i$ 均被 $d$ 整除，可见 $d$ 是 $dif{f}_1$、$dif{f}_2$、$...$、$dif{f}_n?1$ 的公因子，由于 $A_i$ 数列中的最大元素值和最小元素值是固定的，所在数列的公比越大时，所包括的元素个数就越少（可以理解为在一段长度固定的线段中，在某些位置加入点，使得相邻两个点（含首尾）距离都相等。那么很显然，要想点尽可能的少，就要让相邻距离尽可能大。这些点就是数列元素个数，相邻距离就是公差）。

故，以 diff_1、diff_2、…、diff_n-1 的最大公约数作为公差 d 时，能保证 $d$ 取到了满足要求的最大值，所以 { d i f f i } \{diff_i\} {diffi?} 的最大公约数即为最佳原数列对应的公差。

输入数列中最大的元素为 $A_n$，最小元素为 $A_1$，

$A_n?A_1=[a_1+(k_n?1)?d]?[a_1+(k_1?1)?d]=(k_n?k_1)?d$

上面提到过，$k_i$ 的含义与通项公式中的 $n$ 相同，表示的是 $A_i$ 在原数列 { a i } \{a_i\} {ai?} 中排在第几个（从$1$开始），所以 $k_n$ 表示的是 $A_k$ 在 { a i } \{a_i\} {ai?} 中的编号，$k_1$ 表示的是 $A_1$ 在 { a i } \{a_i\} {ai?} 中的编号。

我们要输出的答案是，在数列 { a i } \{a_i\} {ai?} 中 $A_1$ 到 $A_n$ 范围内的个数（含），个数正是 $ k_n - k_1 + 1$，即为答案。

总而言之，答案为，输入数列中最大元素值与最小值之差，除以公差（最大公约数），再加一，算出来的就是答案数列的元素个数。

还有一个遗留问题，如何计算多个数的最大公约数？

Here

需要注意一种特殊的数据，输入的元素存在两个相同（如果输入合法，那么必然输入的元素均相同），则存在 $dif{f}_i=0$，$0$ 与其他任何数是不存在最大公约数，所以需要判断一下输入元素是否都相同，如果都相同，则直接输出 $n$，即最佳数列就是输入数列。

代码

int main()
{
	cin >> n;
	for (int i = 0;i < n;i ++) cin >> a[i];
	sort (a, a+n);
	
	for (int i = 1;i < n;i ++)
		diff.push_back (a[i] - a[i-1]); // 计算两两个数之差
		
	if (diff[0] == 0) { // 特殊情况：如果存在两个数相同，那么整个数列必然都是相同的，所以公差为0，原数列元素个数最少为n 
		cout << n << endl;
		return 0;
	}
	
	int d = __gcd (diff[0], diff[1]); // d 公差
	for (int i = 2;i < diff.size ();i ++) // 计算多个数的公差
		d = __gcd (d, diff[i]);
	
	cout << (a[n-1] - a[0]) / d + 1 << endl;
	
	return 0;
}