d123 - 11063 - B2-Sequence
題目描述
題目要求判斷給定的正整數數列是否為 B2 數列。B2 數列的定義是：數列中的所有元素都是遞增的 (1 <= b1 < b2 < b3 ...)，並且數列中任意兩個元素之和 (bi + bj, i <= j) 都不相等。
解題思路
程式碼首先檢查數列是否遞增且所有元素是否都大於等於 1。如果數列不滿足這個條件，則它不是 B2 數列。如果數列滿足這個條件，程式碼會使用雙重迴圈檢查數列中任意兩個元素之和是否相等。如果找到兩個元素之和相等，則數列不是 B2 數列。使用一個大小為 20001 的陣列 c 來記錄每個和出現的次數。如果任何一個和出現超過一次，則數列不是 B2 數列。
複雜度分析
- 時間複雜度: O(N^2)
- 空間複雜度: O(1) (因為陣列
c的大小是固定的，不依賴於輸入大小 N)
程式碼
#include <iostream>
using namespace std;
int main(){
int N,i=1;;
while(cin >> N){
int a[N],c[20001]={0};
bool ans=0;
for(int i=0;i<N;i++){
cin >> a[i];
if((i!=0&&a[i]<=a[i-1])||a[i]<1)
ans=1;
}
for(int i=0;i<N&&ans!=1;i++){
for(int j=i;j<N&&ans!=1;j++){
c[a[i]+a[j]]++;
if(c[a[i]+a[j]]>1)
ans=1;
}
}
cout << "Case #" << i << ": ";
i++;
(ans==0)?cout << "It is a B2-Sequence.\n\n":cout << "It is not a B2-Sequence.\n\n";
}
}