a274 - 友誼的數字
題目描述
題目要求給定 N 個數字，找到一個排列方式，使得除了前兩個數字以外，每個數字都滿足其左邊兩個數字的和或乘積是它的倍數。如果存在多個解，輸出字典序最小的解。如果無解，則輸出 "No"。
解題思路
這題的解法是使用全排列 (permutation) 暴力搜尋所有可能的排列方式。首先，對輸入的數字進行排序，以便在找到解時直接輸出字典序最小的解。然後，使用 next_permutation 函數生成所有可能的排列。對於每個排列，檢查是否滿足題目中的條件：對於每個數字（從第三個開始），判斷其左邊兩個數字的和或乘積是否是它的倍數。如果所有數字都滿足條件，則輸出該排列並結束搜尋。如果遍歷完所有排列都找不到解，則輸出 "No"。
複雜度分析
- 時間複雜度: O(N! * N)，其中 N 是輸入數字的個數。
next_permutation的時間複雜度是 O(N)，而對於每個排列，需要檢查 N-2 個數字是否滿足條件，每次檢查需要常數時間。 - 空間複雜度: O(N)，主要用於儲存輸入數字的陣列
ans。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long int ans[15];
int n,s;
int main() {
cin.tie(0);cin.sync_with_stdio(0);
while(cin >> n){
for(int i=0;i<n;++i)
cin >> ans[i];
s=0;
sort(ans,ans+n);
do{
int k=0;
for(int i=2;i<n;++i)
if((ans[i-1]+ans[i-2])%ans[i]&&(ans[i-1]*ans[i-2])%ans[i]){
k=1;
break;
}
if(k==0){
s=1;
for(int i=0;i<n;++i)
cout << ans[i] << " ";
cout << "\n";
break;
}
}while(next_permutation(ans,ans+n));
if(s==0)
cout << "No\n";
}
}