2019年省試合第10回ブルーブリッジカップB組C/C++試験問題H解等差数列

試験問題H:等差数列
時間制限:1.0 sメモリ制限:256.0 MB本題総得点:20分【問題説明】数学の先生は明ちゃんに等差数列の和を求める問題を出した.しかし不注意な明ちゃんは一部の数列を忘れ、その中のN個の整数しか覚えていない.今このN個の整数を与えて、明ちゃんはこのN個の整数を含む最も短い等差数列がいくつあることを知りたいですか?【入力フォーマット】入力された第1行は、整数Nを含む.2行目は、N個の整数A 1,A 2,・・,ANを含む.(注意A 1〜ANは必ずしも等差数列の順に与えられるものではない)【出力形式】整数を出力して答えを表す.【サンプル入力】5 2 6 4 10 20【サンプル出力】10【サンプル説明】2、6、4、10、20を含む最短の等差数列は、2、4、6、8、10、12、14、16、18、20である.すべての評価例について、2≦N≦100000、0≦Ai≦109である.
構想:等差数列はn項目を求める:a(n)=a(1)+d*(n-1).公差を求めることができることを知らなければ,再循環累積カウントも答えを得ることができる.

#include
#include
using namespace std;
int main(){
     
 int n,d,ans,a[100005];
 cin>>n;
 for(int i=0;i<n;i++){
     
  cin>>a[i];
 }
 sort(a,a+n);
 d=a[1]-a[0];
 for(int i=1;i<n-1;i++){
      //              
  if(a[i+1]-a[i]<d){
     
   d=a[i+1]-a[i];
  }
 }
 if(d==0){
     
  ans=n;
 }else{
     
  ans=(a[n-1]-a[0])/d+1; //      n ：a(n)=a(1)+d*(n-1)
 }
 cout<<ans<<endl;
 return 0;
}