Hướng dẫn giải của Tìm số lớn nhất
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
Với mỗi truy vấn x, cần max của a1 đến ax. Đây là bài tìm max tiền tố.
Sub 1: Vét cạn - ~O(nq)~, dùng khi ~n, q \le 1000~
Mỗi truy vấn duyệt lại đoạn từ 1 đến x. Đúng 10/10 test.
Sub 2: Mảng max tiền tố - ~O(n + q)~
Đặt pm[i] = max(a1..ai), mỗi truy vấn in pm[x]. Đúng 10/10 test.
Chương trình hoàn chỉnh
main đọc dãy và các truy vấn. Nếu ~n, q \le 1000~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<long long> a;
vector<int> xs;
// Sub 1: vet can - moi truy van duyet lai tu 1 den x. Dung khi n, q <= 1000.
void sub1() {
for (int x : xs) {
long long mx = a[0];
for (int i = 1; i < x; i++) mx = max(mx, a[i]);
cout << mx << "\n";
}
}
// Sub 2: tinh san mang max tien to pm[i] = max(a_1..a_i), moi truy van tra loi O(1).
void sub2() {
vector<long long> pm(n);
pm[0] = a[0];
for (int i = 1; i < n; i++) pm[i] = max(pm[i - 1], a[i]);
for (int x : xs) cout << pm[x - 1] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (auto& v : a) cin >> v;
cin >> q;
xs.resize(q);
for (auto& x : xs) cin >> x;
if (n <= 1000 && q <= 1000) sub1();
else sub2();
return 0;
}
Bình luận