2019年蓝桥杯C/C++ B组省赛试题H：等差数列题解

清疚 2022-12-28 14:17 162阅读 0赞

### 文章目录 ###

*  题目描述
 *  解题代码
 *   *  暴力算法
     *   *  时间复杂度是O(mmin \* n)
     *  gcd最大公约数
     *   *  时间复杂度是O(logmax(a,b) \* n)

--------------------

# 题目描述 #

![题目][05by5j.png]

# 解题代码 #

## 暴力算法 ##

> 经过分析可以知道，排序后的数列中，每两个数之间都存在一个差，**所有的差最小的`mmin`那个才有可能会是公差（因为如果公差比最小的还要大，那么中间就会至少越过一项，不满足等差数列）**

因此只需要将公差`mmin ~ 0`进行遍历即可找到使得等差数列最短的公差

**存在超时风险！！！！**

//
    //  main.cpp
    //  2019lanqiao-h
    //
    //  Created by 陈洋 on 2020/10/8.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int a[200005];
    
    int main(int argc, const char * argv[]) {
        
        int n;
        
        cin >> n;
        
        for(int i = 0; i < n; i++)  cin >> a[i];
        
        sort(a, a + n);
        
    //    for(int i = 0; i < n; i++) cout << a[i] << endl;
        int mmin = -1;
    		
    		//找到两个数之间最小的差
        for(int i = 0; i < n - 1; i++){
        
            int temp = a[i + 1] - a[i];
    
            if(mmin == -1 || mmin > temp) mmin = temp;
        }
      	//找到两个数之间最小的差
    
        int ans = -1;
        
      	//从1到两个数之间最小的差，依次测试公差
        for(int i = mmin; i >= 1; i--){
        
            int j = 1;
            for(j = 1; j < n; j++){
        
                if((a[j] - a[0]) % i != 0)
                    break;
            }
            
            if(j == n){
        
                ans = (a[n - 1] - a[0]) / i + 1;
                break;
            }
        }
      	
      	//ans == -1说明公差为0
        if(ans == -1)   ans = n;
        
        cout << ans << endl;
        
        return 0;
    }

### 时间复杂度是O(mmin \* n) ###

## gcd最大公约数 ##

我们可以知道等差数列中的每个项的组成为`an = a1 + (n - 1) * d`

由此可知**ai** 与**aj** 之间会差`(j - i) * d`

因此我不需要管当前数列的排列，计算出每两个项之间的差，求出他们的最大公约数，就可以的到最大公差。

//
    //  main.cpp
    //  2019lanqiao-h
    //
    //  Created by 陈洋 on 2020/10/8.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    //gcd
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    typedef long long ll;
    int a[200005];
    int n;
    
    ll gcd(ll a, ll b)
    {
        
        if(a < b) return gcd(b, a);
        if(b == 0) return a;
        return gcd(b, a % b);
    }
    
    int main(){
        
        cin >> n;
        
        for(int i = 0; i < n; i++)  cin >> a[i];
        
        sort(a, a + n);
        
      	//算出所有差的最大公约数
        int GCD = 0;
        for(int i = 0; i < n - 1; i++){
        
            if(i == 0){
        
                GCD = a[i + 1] - a[i];
            }
            else{
        
                int temp = a[i + 1] - a[i];
                GCD = gcd(GCD, temp);
            }
        }
      	//算出所有差的最大公约数
        
        if(GCD == 0)
            cout << n << endl;
        else{
        
            cout << (a[n - 1] - a[0]) / GCD + 1 << endl;
        }
        
        return 0;
    }

### 时间复杂度是O(logmax(a,b) \* n) ###

[05by5j.png]: /images/20221120/6fd5bf19a8974618a80bd1d827373e72.png