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

题目： 如果一个数列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

解题思路： 在各种各样的编程题中，有些是直接给出要求，比如从尾到头打印链表，我们只看题目就可以一抹了然，数据结构是链表，要求是从后向前打印。但是有时给的更像是一个应用题，这就好比小学时一个水管放水，一个水管注水的问题一样，好神奇…..这是网易的一道题目，说了半天就是要判断一列数字是不是等差数列，由于没有插入与删除操作，一个顺序存储结构就可以啦。 我们可以试着这样来解决，找到一列数（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;
}