P8682题解

· · 题解

题目传送门

参考了一下 楼上的题解

大概思路

因为我们常见的等差数列一般都是有序的，所以我们可以先将数组排个序，这样也方便我们后续的处理。

又因为题目说是让我们求出最短的等差数列。

则我们一定要使得公差尽可能大。

那么完整的等差数列是不可能有数大于 \max\limits_{i=1}^n a_i 或小于 \min\limits_{i=1}^n a_i 的。

换句话说， a_1 就是等差数列的首项， a_n 就是等差等差数列的末项。

又因为等差数列中每两项的差都可以表示为公差的倍数。

所以等差数列中的每一对 a_i，a_j，(i<j)。

可以得出 a_j-a_i=(j-i) d。

其中 d 表示公差。

根据上面的式子，我们可以得出结论:

最大的公差 d 其实就是原数列中所有相邻两项的差的最大值。

则答案就是 \dfrac{a_n-a_i}{d}+1。

根据上面的分析，我们可以写出以下代码。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    int d=a[n]-a[1];
    for(int i=2;i<=n-1;i++) d=__gcd(d,a[i+1]-a[i]);         
    cout<<(a[n]-a[1])/d+1;
}

但是如果提交上面的代码，你就会发现会 RE一个点，为什么呢？

我们再看回代码就会发现：

在最后一行有一个 (a[n]-a[1])/d+1 ，那要是最后我们求出的 d 为零，那不就 RE 了吗？

所以，我们可以加上一个特判。

最终代码

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    if(a[1]==a[n]){
        cout<<n;
        return 0;
    }
    int d=a[n]-a[1];
    for(int i=2;i<=n-1;i++) d=__gcd(d, a[i+1]-a[i]);        
    cout<<(a[n]-a[1])/d+1;
}