Hướng dẫn giải của [VT Thiếu nhi] BÀI 01: SORT
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
Sắp xếp nửa đầu (nửa đầu gồm ~\lceil n/2 \rceil~ phần tử) giảm dần, nửa sau tăng dần.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Sắp xếp mỗi nửa bằng bubble sort. Bộ test chấm đều có ~n \ge 15000~ nên sub này không ăn được test nào (0/20), nhưng đúng với hai ví dụ trong đề và là cách chắc chắn khi dữ liệu nhỏ.
Sub 2: Sắp xếp thư viện — ~O(n \log n)~
Dùng sort của thư viện: nửa đầu sort giảm dần, nửa sau sort tăng dần. Đúng với mọi test (20/20).
Chương trình hoàn chỉnh
Chương trình đọc ~n~; nếu ~n \le 5000~ gọi sub1, còn lại gọi sub2.
Chương trình đầy đủ đúng 20/20 test; vì mọi test đều lớn hơn miền của sub 1 nên sub 1 được kiểm tra bằng ví dụ trong đề.
#include <bits/stdc++.h>
using namespace std;
int n, h; // h = so phan tu cua nua dau = (n+1)/2 (neu n le, phan tu giua thuoc nua dau)
int a[100005];
// Sub 1: vet can. Nua dau sap giam, nua sau sap tang, moi nua bang bubble sort. O(n^2)
// Dung khi n <= 5000
void sub1() {
// Nua dau a[1..h]: giam dan
for (int i = 1; i <= h; i++)
for (int j = 1; j < h; j++)
if (a[j] < a[j + 1]) swap(a[j], a[j + 1]);
// Nua sau a[h+1..n]: tang dan
for (int i = h + 1; i <= n; i++)
for (int j = h + 1; j < n; j++)
if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
// Sub 2: day du. Dung sort cua thu vien, O(n log n). Nua dau sort giam, nua sau sort tang.
void sub2() {
sort(a + 1, a + h + 1, greater<int>());
sort(a + h + 1, a + n + 1);
}
int main() {
freopen("SORT.INP", "r", stdin);
freopen("SORT.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
h = (n + 1) / 2;
if (n <= 5000) sub1();
else sub2();
for (int i = 1; i <= n; i++) cout << a[i] << (i < n ? ' ' : '\n');
return 0;
}
Bình luận