Hướng dẫn giải của [200 đề thầy Đức] Bài 189: Khoảng cách xa 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 giá trị, khoảng cách xa nhất giữa hai vị trí có cùng giá trị là vị trí cuối trừ vị trí đầu. Đáp án là giá trị lớn nhất của các khoảng cách này; nếu không có cặp nào bằng nhau thì in 0.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 500~
Thử mọi cặp ~i < j~ có ~a_i = a_j~ và giữ ~j - i~ lớn nhất. Nếu chỉ nộp sub này: đúng 21/21 test.
Sub 2: Vị trí đầu và cuối — ~O(n)~
Ghi lại vị trí xuất hiện đầu tiên và cuối cùng của mỗi giá trị (giá trị không quá ~10^4~), rồi lấy max của hiệu cuối trừ đầu. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~T~ bộ dữ liệu. Với mỗi bộ, nếu ~N \le 500~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[10005];
// Sub 1: vét cạn O(n^2). Thử mọi cặp (i, j) có a[i] = a[j], lấy khoảng cách lớn nhất.
void sub1() {
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i] == a[j]) ans = max(ans, j - i);
printf("%d\n", ans);
}
// Sub 2: O(n). Với mỗi giá trị, chỉ cần vị trí xuất hiện đầu tiên và cuối cùng.
void sub2() {
vector<int> first(10005, 0), last(10005, 0);
for (int i = 1; i <= n; i++) {
if (!first[a[i]]) first[a[i]] = i;
last[a[i]] = i;
}
int ans = 0;
for (int v = 1; v <= 10000; v++)
if (first[v]) ans = max(ans, last[v] - first[v]);
printf("%d\n", ans);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 500) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
}
return 0;
}
Bình luận