Hướng dẫn giải của [200 đề thầy Đức] Bài 166: Phần tử lãnh đạo
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ìm tất cả phần tử lãnh đạo của dãy, tức các phần tử lớn hơn mọi phần tử đứng bên phải nó (phần tử cuối luôn là lãnh đạo). In chúng theo thứ tự từ trái sang phải.
Sub 1: Vét cạn — ~O(N^2)~
Với mỗi vị trí i, kiểm tra lần lượt các phần tử j > i. Nếu gặp A[j] >= A[i] thì A[i] không phải lãnh đạo. Đạ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;
bool first = true;
// Vét cạn: với mỗi i, kiểm tra mọi phần tử đứng bên phải
for (int i = 0; i < n; i++) {
bool leader = true;
for (int j = i + 1; j < n; j++) {
if (a[j] >= a[i]) {
leader = false;
break;
}
}
if (leader) {
if (!first) cout << ' ';
cout << a[i];
first = false;
}
}
cout << "\n";
}
return 0;
}
Sub 2: Duyệt từ phải sang trái — ~O(N)~
Duyệt từ cuối dãy về đầu, giữ lại giá trị lớn nhất mx đã gặp. Một phần tử A[i] là lãnh đạo khi A[i] > mx; khi đó cập nhật mx = A[i]. Các phần tử thu được đang ngược thứ tự, nên cần đảo lại trước khi in.
Bẫy cần chú ý: phải so sánh nghiêm ngặt > vì đề yêu cầu lớn hơn; giá trị khởi tạo mx là số nhỏ nhất (LLONG_MIN) để phần tử cuối luôn được tính. Đạ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;
// Duyệt từ phải sang trái, giữ max các phần tử đã gặp.
// Phần tử lãnh đạo là phần tử lớn hơn max bên phải nó.
vector<long long> res;
long long mx = LLONG_MIN;
for (int i = n - 1; i >= 0; i--) {
if (a[i] > mx) {
res.push_back(a[i]);
mx = a[i];
}
}
// Các phần tử thu được đang theo thứ tự phải -> trái, đảo lại
reverse(res.begin(), res.end());
for (int i = 0; i < (int)res.size(); i++) {
if (i) cout << ' ';
cout << res[i];
}
cout << "\n";
}
return 0;
}
Bình luận