建模-判断一列数是不是等差数列

清疚 2022-06-10 10:14 108阅读 0赞

**题目：**  
如果一个数列S满足对于所有的合法的i,都有S\[i + 1\] = S\[i\] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。  
小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列。

输入要求：  
输入包括两行,第一行包含整数n(2 ≤ n ≤ 50),即数列的长度；第二行n个元素x\[i\](0 ≤ x\[i\] ≤ 1000),即数列中的每个整数。

输出要求：  
如果可以变成等差数列输出”Possible”,否则输出”Impossible”。

例如  
输入：  
3  
3 1 2  
输出：  
Possible

**解题思路：**  
在各种各样的编程题中，有些是直接给出要求，比如[从尾到头打印链表][Link 1]，我们只看题目就可以一抹了然，数据结构是链表，要求是从后向前打印。但是有时给的更像是一个应用题，这就好比小学时**一个水管放水，一个水管注水的问题一样，好神奇…..**这是网易的一道题目，说了半天就是要判断一列数字是不是等差数列，由于没有插入与删除操作，一个顺序存储结构就可以啦。  
我们可以试着这样来解决，找到一列数（n个）中的最大max和最小min，如果max=min，则为公差为0的等差数列，如果不相等那么公差就是max-min/n-1，如果没办法除尽的话，那么不是等差数列，如果除尽，即求出公差error。  
现在我们知道了一个数列的最大值，最小值，个数和公差，这样就知道了等差数列的每一个数，那么下面就可以逐个判断这些数是不是在数组中，由于不是排序的数组，二分法啥的也就用不了了，所以时间复杂度是O(n^2)，那么有没有其他的方法可以优化时间复杂度呢？  
由于我们知道数组中的最小值，那么如果是等差数列的话，数组中的每个数与最小值的差值，对error取模的结果应该都是0，这样我们就可以判断一列数是不是等差数列了，时间复杂度为O(n)。

**代码实现：**

#include "iostream"    
    using namespace std;
    
    int main()
    {
        int str[50];
        int num;
        cin>>num;
        for (int i = 0;i<num;i++)
            cin>>str[i];
        int maxvalue =0;
        for (int i = 0;i<num;i++)
        {
            if (maxvalue<str[i])
              maxvalue=str[i];
        }
        int minvalue =maxvalue;
        for (int i = 0;i<num;i++)
        {
            if (minvalue>str[i])
                minvalue=str[i];
        }
        if (maxvalue==minvalue)
        {
            cout<<"Possible"<<endl ;
            return 0;
        }
        int flag =  (maxvalue-minvalue)%(num-1);
        if (flag != 0)
        {
                cout<<"Impossible"<<endl ;
                return 0;
        }
        int error =(maxvalue-minvalue)/(num-1);
        for (int j=0;j <num;j++)
        {
            if ((str[j]-minvalue)%error !=0)
                cout<<"Impossible"<<endl;
        }
        cout<<"Possible"<<endl;
        return 0;
    }

[Link 1]: http://blog.csdn.net/chaipp0607/article/details/76737478