Hướng dẫn giải của [200 đề thầy Đức] Bài 186: Thành phố đẹp
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 cặp nhà khác màu có khoảng cách ~j - i~ lớn nhất.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 2000~
Thử mọi cặp ~i < j~ có màu khác nhau, lấy khoảng cách lớn nhất. Nếu chỉ nộp sub này: đúng 11/21 test.
Sub 2: Xét hai đầu mút — ~O(n)~
Cặp xa nhất luôn chứa một đầu mút là nhà 1 hoặc nhà ~N~. Với nhà 1, tìm nhà ~j~ xa nhất có màu khác màu nhà 1, khoảng cách là ~j - 1~. Với nhà ~N~, tìm nhà ~i~ nhỏ nhất có màu khác màu nhà ~N~, khoảng cách là ~N - i~. Lấy giá trị lớn hơn. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~N~ và màu các nhà. Nếu ~N \le 2000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
int c[300005]; // màu các ngôi nhà (đánh số từ 1)
// Sub 1: vét cạn O(n^2). Thử mọi cặp (i, j), i < j, có màu khác nhau.
void sub1() {
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (c[i] != c[j]) ans = max(ans, j - i);
printf("%d\n", ans);
}
// Sub 2: O(n). Cặp xa nhất luôn chứa một đầu mút: hoặc nhà 1, hoặc nhà N.
// Với nhà 1: tìm nhà j xa nhất có màu khác c[1]. Với nhà N: tìm nhà i xa nhất có màu khác c[N].
void sub2() {
int ans = 0;
for (int j = n; j >= 1; j--)
if (c[j] != c[1]) {
ans = max(ans, j - 1);
break;
}
for (int i = 1; i <= n; i++)
if (c[i] != c[n]) {
ans = max(ans, n - i);
break;
}
printf("%d\n", ans);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> c[i];
if (n <= 2000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận