Hướng dẫn giải của [200 đề thầy Đức] Bài 167: Dãy trật tự luân phiê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
Cho dãy N số nguyên khác nhau, cần sắp lại theo thứ tự: số lớn nhất, số nhỏ nhất, số lớn thứ hai, số nhỏ thứ hai, … Với N ≤ 10^5 cần cách sắp xếp nhanh.
Sub 1: Vét cạn — ~O(N^2)~
Mỗi bước, quét các phần tử chưa dùng để tìm lớn nhất (bước lẻ) hoặc nhỏ nhất (bước chẵn), đưa vào kết quả và đánh dấu đã dùng. Cách này đúng nhưng mỗi bước tốn O(N), nên với N lớn chỉ đạt 1/21 test, còn lại quá giờ.
#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<long long> a(n);
for (auto &x : a) cin >> x;
vector<bool> used(n, false);
vector<long long> res;
// Vét cạn: mỗi lần tìm lớn nhất rồi nhỏ nhất trong các phần tử chưa dùng
for (int step = 0; step < n; step++) {
bool takeMax = (step % 2 == 0);
int pick = -1;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
if (pick == -1 || (takeMax ? a[i] > a[pick] : a[i] < a[pick])) pick = i;
}
used[pick] = true;
res.push_back(a[pick]);
}
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
cout << res[i];
}
cout << "\n";
}
return 0;
}
Sub 2: Sắp xếp rồi dùng hai con trỏ — ~O(N log N)~
Sắp xếp dãy tăng dần. Đặt con trỏ lo ở đầu và hi ở cuối. Lần lượt lấy a[hi--] (lớn nhất còn lại) rồi a[lo++] (nhỏ nhất còn lại), xen kẽ cho đến khi lấy hết N số. Đạ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<long long> a(n);
for (auto &x : a) cin >> x;
// Sắp xếp tăng dần, sau đó lấy lần lượt lớn nhất, nhỏ nhất bằng hai con trỏ
sort(a.begin(), a.end());
int lo = 0, hi = n - 1;
bool takeMax = true;
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
if (takeMax) cout << a[hi--];
else cout << a[lo++];
takeMax = !takeMax;
}
cout << "\n";
}
return 0;
}
Bình luận