Hướng dẫn giải của [200 đề thầy Đức] Bài 150: Sắp xếp mảng nhị phân
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
Dãy chỉ gồm số 0 và 1. Sau khi sắp xếp tăng dần, mọi số 0 đứng trước, các số 1 đứng sau. Chỉ cần đếm số 0 rồi in ra.
Sub 1: Sắp xếp bằng std::sort — ~O(N \log N)~
Đọc dãy, dùng sort để sắp xếp trực tiếp. Đạt 19/21 test, 2 test lớn quá giờ vì N lên tới 10^6 nên ~O(N log N)~ chậm.
#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> a(n);
for (int &x : a) cin >> x;
// Sắp xếp trực tiếp dãy 0/1 bằng std::sort
sort(a.begin(), a.end());
for (int x : a) cout << x << " ";
cout << "\n";
}
return 0;
}
Sub 2: Đếm số 0 — ~O(N)~
Đếm số 0 là ~zeros~, sau đó in ~zeros~ số 0 rồi đến ~N - zeros~ số 1. Mỗi số kèm dấu cách theo đúng định dạng đề. Đạ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;
// Đếm số 0, các số 0 đứng trước các số 1 sau khi sắp xếp
int zeros = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x == 0) zeros++;
}
// In zeros số 0 rồi đến n - zeros số 1, mỗi số kèm dấu cách
for (int i = 0; i < n; i++) cout << (i < zeros ? 0 : 1) << " ";
cout << "\n";
}
return 0;
}
Bình luận