Hướng dẫn giải của [200 đề thầy Đức] Bài 156: Tách dãy chẵn lẻ
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Tách dãy ~A~ thành dãy số chẵn và dãy số lẻ, sắp xếp mỗi dãy tăng dần, rồi in dãy chẵn trước, dãy lẻ sau. Mỗi bộ dữ liệu in một dòng, các số cách nhau bằng dấu cách.
Sub 1: Sắp xếp bằng selection sort — ~O(N^2)~
Tách số chẵn và lẻ vào hai vector, sau đó sắp xếp mỗi vector bằng selection sort (mỗi lần tìm số nhỏ nhất rồi đổi chỗ). Đạt 13/21 test, 8 test lớn quá giờ vì N lên tới 10^5.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> ev, od;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) ev.push_back(x);
else od.push_back(x);
}
// Vét cạn O(N^2): sắp xếp từng dãy bằng selection sort
for (vector<int> *v : {&ev, &od}) {
int m = v->size();
for (int i = 0; i < m; i++) {
int mn = i;
for (int j = i + 1; j < m; j++) if ((*v)[j] < (*v)[mn]) mn = j;
swap((*v)[i], (*v)[mn]);
}
}
for (int x : ev) cout << x << " ";
for (int x : od) cout << x << " ";
cout << "\n";
}
return 0;
}
Sub 2: Sắp xếp bằng std::sort — ~O(N \log N)~
Thay selection sort bằng sort của thư viện chuẩn, độ phức tạp ~O(N \log N)~ đủ nhanh cho N = 10^5. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> ev, od;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) ev.push_back(x); // dãy chẵn
else od.push_back(x); // dãy lẻ
}
sort(ev.begin(), ev.end());
sort(od.begin(), od.end());
for (int x : ev) cout << x << " ";
for (int x : od) cout << x << " ";
cout << "\n";
}
return 0;
}
Bình luận