藍(lán)橋杯[十一屆][B組]-等差數(shù)列
2022-03-31 23:23 幻霞 閱讀(41) 評(píng)論(0) 收藏 舉報(bào)
題目比較簡(jiǎn)單,但是考察一些數(shù)學(xué)知識(shí)。
#include<bits/stdc++.h> #include<string.h> using namespace std; int num[100005]={0}; int cmp(const void* a,const void* b){ return *(int*)a-*(int*)b; } int main(){ ios::sync_with_stdio(false), cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ cin>>num[i]; } qsort(num,n,sizeof(int),cmp); int minv=num[0],maxv=num[n-1],mind=maxv; for(int i=1;i<n;i++){ mind=min(mind,num[i]-num[i-1]); } if(mind==0) cout<<n; else cout<<(maxv-minv)/mind + 1; return 0; }
思路:排個(gè)序,算出最大最小值,然后再得到排序數(shù)組的最小鄰差(即最小公差)
如果最小公差為0,即為常數(shù)列,那值便就是n,如果不為一,那就有等差數(shù)列求項(xiàng)數(shù)和(max-min)/d + 1
這里寫了一個(gè)stdlib庫(kù)中的快排算法,還有cmp比較函數(shù)的定義,以后會(huì)經(jīng)常用到,不妨記一下或再看一下。
浙公網(wǎng)安備 33010602011771號(hào)