Hướng dẫn giải của TKNP02: Tìm X
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 đã sắp xếp tăng dần. Với mỗi ~X~, in vị trí xuất hiện đầu tiên (đánh số từ 1), hoặc -1 nếu ~X~ không có trong dãy.
Sub 1: Vét cạn — ~O(n \cdot Q)~, dùng khi ~n \cdot Q \le 10^7~
Quét từ đầu dãy, gặp ~X~ đầu tiên thì ghi lại vị trí và dừng. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Tìm nhị phân (lower_bound) — ~O(Q \log n)~
Vì dãy đã sắp xếp, ~lower_bound~ cho vị trí đầu tiên có giá trị không nhỏ hơn ~X~. Kiểm tra giá trị tại đó có đúng bằng ~X~ không. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc dữ liệu. Nếu ~n \cdot Q \le 10^7~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, Q;
vector<long long> A;
vector<long long> qs;
// Sub 1: vet can. Moi truy van duyet tu dau day, gap X dau tien thi in vi tri (1-based). O(n*Q).
void sub1() {
for (long long x : qs) {
int pos = -1;
for (int i = 0; i < n && pos < 0; i++)
if (A[i] == x) pos = i + 1;
cout << pos << "\n";
}
}
// Sub 2: day da sap xep tang dan, dung lower_bound tim vi tri dau tien >= X. O(Q log n).
void sub2() {
for (long long x : qs) {
int idx = lower_bound(A.begin(), A.end(), x) - A.begin();
if (idx < n && A[idx] == x) cout << idx + 1 << "\n";
else cout << -1 << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> Q;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
qs.resize(Q);
for (int i = 0; i < Q; i++) cin >> qs[i];
if ((long long)n * Q <= 10000000) sub1();
else sub2();
return 0;
}
Bình luận