f410 - 芝麻街的郵件投遞
題目描述
題目要求模擬郵差 Barney 投遞郵件的順序。給定一組門牌號碼，需要將雙號郵件從小到大排序後輸出，再將單號郵件從大到小排序後輸出。
解題思路
解題思路是將輸入的門牌號碼分成兩組：雙數和單數。分別對兩組數進行排序。雙數從小到大排序，單數從大到小排序。最後，先輸出排序後的雙數組，再輸出排序後的單數組。使用了兩個陣列 e 和 o 分別儲存雙數和單數，eit 和 oit 追蹤雙數和單數的數量。sort 函式用於排序。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int a[1001],o[1001],e[1001],oit,eit,n;
int main() {
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i];
if(a[i]%2){
o[oit]=a[i];
++oit;
}
else{
e[eit]=a[i];
++eit;
}
}
sort(o,o+oit);
sort(e,e+eit);
for(int i=0;i<eit;++i){
cout << e[i] << " ";
}
for(int i=oit-1;i>=0;--i){
cout << o[i] << " ";
}
}