P8682 等差数列

· · 题解

P8682 等差数列

题目传送门

这道题不难，但还是要分析一下。

首先，为了项数最少，我们一定不会在添加比数据中最小值还小或者比最大值还大的数。

这就意味着我们已经知道了最终等差数列的首项和末项，所以我们只需求出公差即可。

为了使项数最少，我们需要公差尽可能地大。

不妨设等差数列为单调不减数列。

则对于等差数列 a 中任意两项 a_i,a_j（i<j）。

有 a_j-a_i = (a_{j-1}+d)-a_i = (a_{j-2}+2d)-a_i = … =[a_{i+1}+(j-i-1)d]-a_i = (j-i)d。

所以任意两项的差均为公差 d 的倍数，于是所求 d 为所有相邻两项差的公约数。又因为 d 要最大，所以 d 就是所有相邻两项差的最大公约数。

分析结束，上代码。

#include<bits/stdc++.h>
using namespace std;

int n;
int a[100005];
int d;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);//题目明确说了“不一定按顺序给出”，所以要先排序
    d = a[2]-a[1];
    if(d == 0){//如果d=0，那么说明所有的数都相等，最小个数肯定就是n 
        cout << n;
        return 0;
    }
    for(int i = 2; i <= n-1; i++){
        d = __gcd(d, a[i+1]-a[i]);//求所有差的最大公约数 
    }
    cout << (a[n]-a[1])/d+1;//算出项数，输出 
    return 0;
}