AcWing 1246. 等引數列
數學老師給小明出了一道等引數列求和的題目，
但是粗心的小明忘記了一部分的數列，只記得其中 N 個整數，
現在給出這 N 個整數，小明想知道包含這 N 個整數的最短的等引數列有幾項？
輸入格式
輸入的第一行包含一個整數 N，
第二行包含 N 個整數 A1,A2,???,AN，(注意 A1～AN 并不一定是按等引數
列中的順序給出)
輸出格式
輸出一個整數表示答案，
資料范圍
2≤N≤100000,
0≤Ai≤109
輸入樣例：
5
2 6 4 10 20
輸出樣例：
10
樣例解釋
包含 2、6、4、10、20 的最短的等引數列是 2、4、6、8、10、12、14、16、18、20，
難度： 中等
時/空限制： 1s / 64MB
總通過數： 1184
總嘗試數： 3318
來源： 第十屆藍橋杯省賽C++B/C組,第十屆藍橋杯省賽JAVAC組
演算法標簽
這道題給的資料比較亂，所以我們第一步首先要對樣例進行一個排序操作，
然后我們觀察相鄰的兩個數的差一定是公差的倍數，于是我想到用求最小公約數求公差，
這是我的思路，在寫代碼的時候也遇到了不少問題，
這是我的第一次代碼
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int gcd(int a,int b)
{
if(!b) return a;
else gcd(b,a%b);
}
int main(void)
{
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]<<" ";
// puts("");
int t=a[1]-a[0];
for(int i=2;i<n;i++)
t=gcd(t,a[i]-a[i-1]);
cout<<(a[n-1]-a[0])/t+1;
}
這個代碼看上去應該是沒有問題的，我測驗了樣例沒有問題，但是這個題給的評測資料有一點點讓人感到苛刻，我出現了一個浮點錯誤，這是分母為0 造成的錯誤，
可以觀察到這個測驗資料的公差是0，我也沒有預料到會有這種情況，而且卡在了第18個資料上，然后我迅速做出改動，改變了使用公差的條件，代碼如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int gcd(int a,int b)
{
if(!b) return a;
else gcd(b,a%b);
}
int main(void)
{
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]<<" ";
// puts("");
int t=a[1]-a[0];
for(int i=2;i<n;i++)
t=gcd(t,a[i]-a[i-1]);
if(t)
cout<<(a[n-1]-a[0])/t+1;
else
cout<<n;
}
然后這個代碼就成功AC了，做完這道題我感嘆要考慮到所有的資料才能不被考官抓住把柄，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266728.html
標籤：其他
上一篇：高度集成外圍電路的無線物聯網WiFi串口模塊—MT7628NN硬路由模塊
下一篇：毫米波雷達使用仿真學習實體