[牛客网]等差数列

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

代码

#include<iostream>
using namespace std;
   class Solution
{
public:
   void Dengcha()
   {
       int n;
       int d;
       int sum=0;
       cin>>n;
       int *a=new int[n];
       for(int i=0;i<n;i++)
           cin>>a[i];
       for(int i=0;i<n;i++)
       {
           for(int j=n-2;j>=i;j--)
           {
               if (a[j]>a[j+1])
               {            
                   int temp=a[j];
                   a[j]=a[j+1];
                   a[j+1]=temp;
               }
           }
        }
       d=a[1]-a[0];
       for(int i=1;i<n;i++)
       {
           if( a[i]+d==a[i+1])
               sum++;
       }   
       if (sum==n-2)
           cout<<"Possible"<<endl;
       else
           cout<<"Impossible"<<endl;
   }
   
};
int main()
{
   Solution s;
   s.Dengcha();   
}

算法

首先对数列中的数进行排序，然后算出前两个数的差，即假定为方差，然后再对每个数检验。

改进

其中排序算法可以用sort函数代替

sort(a,a+n);

但是要引入 algorithm的头文件。