Hướng dẫn giải của [Beginner Free Contest 13] RBPOINT2
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 khoảng cách nhỏ nhất giữa một điểm xanh và một điểm đỏ bất kỳ. Sắp xếp các điểm đỏ rồi tìm điểm gần nhất cho từng điểm xanh.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Thử mọi cặp điểm xanh và đỏ. Nếu chỉ nộp sub này: đúng 5/10 test.
Sub 2: Sắp xếp và tìm nhị phân — ~O(n \log n)~
Sắp xếp điểm đỏ, với mỗi điểm xanh dùng ~lower_bound~ để xét điểm đỏ ngay bên phải và bên trái. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
~main~ đọc dữ liệu, nếu ~n \le 1000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> b, r;
// Sub 1: vet can O(n^2) (n <= 1000): thu moi cap (diem xanh, diem do)
void sub1() {
long long best = LLONG_MAX;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
best = min(best, llabs(b[i] - r[j]));
cout << best << "\n";
}
// Sub 2: O(n log n): sap xep diem do, voi moi diem xanh tim diem do gan nhat bang lower_bound
void sub2() {
sort(r.begin(), r.end());
long long best = LLONG_MAX;
for (int i = 0; i < n; i++) {
auto it = lower_bound(r.begin(), r.end(), b[i]);
if (it != r.end()) best = min(best, *it - b[i]);
if (it != r.begin()) best = min(best, b[i] - *prev(it));
}
cout << best << "\n";
}
int main() {
cin >> n;
b.resize(n);
r.resize(n);
for (auto &x : b) cin >> x;
for (auto &x : r) cin >> x;
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận