a251 - 假費波那契數
題目描述
題目要求生成一個偽費波那契數列，數列的生成規則是每個數等於前一個數加上四個數前的數。給定數列的長度 N 和前四個數，輸出數列的中位數。
解題思路
首先，根據題目描述，生成指定長度的偽費波那契數列。數列的生成從第五個數開始，每個數等於前一個數加上四個數前的數。生成數列後，對數列進行排序。由於 N 是奇數，中位數就是排序後數列中 N/2 位置的元素。
複雜度分析
- 時間複雜度: O(N log N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int t,N;
cin >> t;
while(t--){
cin >> N;
int a[N]={0};
cin >> a[0] >> a[1] >> a[2] >> a[3];
for(int i=4;i<N;i++)
a[i]=a[i-1]+a[i-4];
sort(a,a+N);
cout << a[N/2] << "\n";
}
}