Hướng dẫn giải của Khoảng cách nhỏ nhất
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, ,
Editorial for rbpoint2: Khoảng cách nhỏ nhất
Hiểu bài toán
Bài toán yêu cầu tìm khoảng cách nhỏ nhất giữa một điểm xanh và một điểm đỏ trên trục tọa độ. Input gồm n điểm xanh (tọa độ bi) và n điểm đỏ (tọa độ ri). Khoảng cách giữa hai điểm x và y được định nghĩa là |x - y|. Ta cần tìm min{|bi - rj|} với mọi i, j trong khoảng [1, n].
Các cách tiếp cận
Cách Brute Force (Đối sánh mọi cặp)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int main() {
int n;
scanf("%d", &n);
int b[n], r[n];
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &r[i]);
long long min_dist = LLONG_MAX;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long long dist = abs((long long)b[i] - r[j]);
if (dist < min_dist) min_dist = dist;
}
}
printf("%lld", min_dist);
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Phương pháp này duyệt qua tất cả các cặp điểm xanh - đỏ có thể và tính khoảng cách, cập nhật giá trị nhỏ nhất. Với n lên tới 10^5, độ phức tạp O(n^2) là quá lớn (khoảng 10^10 phép tính) và chắc chắn sẽ gây ra lỗi Time Limit Exceeded.
Cách Binary Search (Tìm kiếm nhị phân)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int n;
scanf("%d", &n);
int b[n], r[n];
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &r[i]);
qsort(b, n, sizeof(int), cmp);
qsort(r, n, sizeof(int), cmp);
long long min_dist = LLONG_MAX;
// Duyệt qua mảng xanh, tìm giá trị đỏ gần nhất trong mảng đỏ đã sắp xếp
for (int i = 0; i < n; i++) {
int key = b[i];
// Sử dụng binary search (bsearch) hoặc tự implement
// Tìm vị trí chèn hoặc phần tử đầu tiên >= key
// Ở đây minh họa logic đơn giản
int *found = (int*)bsearch(&key, r, n, sizeof(int), cmp);
if (found != NULL) {
long long d = abs((long long)key - *found);
if (d < min_dist) min_dist = d;
}
// Kiểm tra phần tử bên trái của found
int idx = (int)((long*)found - (long*)r);
if (idx > 0) {
long long d = abs((long long)key - r[idx-1]);
if (d < min_dist) min_dist = d;
}
}
printf("%lld", min_dist);
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Sau khi sắp xếp cả hai mảng, ta duyệt qua mỗi điểm xanh và dùng Binary Search để tìm điểm đỏ gần nhất trong mảng đỏ. Độ phức tạp là O(n log n) do sort và tìm kiếm. Đây là cách tiếp cận hợp lý nhưng vẫn chưa tối ưu nhất về mặt code ngắn gọn và tốc độ xử lý dữ liệu lớn.
Cách Two Pointers (Hai con trỏ)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int n;
scanf("%d", &n);
long long a[100005], b[100005];
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
for (int i = 0; i < n; i++) scanf("%lld", &b[i]);
qsort(a, n, sizeof(long long), cmp);
qsort(b, n, sizeof(long long), cmp);
long long min = 2000000000LL; // 2e9
int i = 0, j = 0;
while (i < n && j < n) {
long long diff = a[i] - b[j];
long long abs_diff = diff < 0 ? -diff : diff;
if (abs_diff < min) min = abs_diff;
if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
printf("%lld", min);
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Sau khi sắp xếp cả hai mảng tăng dần, ta sử dụng hai con trỏ i (cho mảng xanh) và j (cho mảng đỏ). Ta so sánh a[i] và b[j]:
- Nếu a[i] < b[j], khoảng cách sẽ giảm nếu ta tăng i (vì a[i+1] lớn hơn但仍小于 b[j] hoặc gần hơn).
- Nếu a[i] >= b[j], ta tăng j. Trong mỗi bước, ta cập nhật khoảng cách nhỏ nhất. Độ phức tạp dominated bởi việc sort O(n log n), phần duyệt hai con trỏ chỉ là O(n).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) | O(n) | Brute Force (Đối sánh mọi cặp) |
| 2 | O(n log n) | O(n) | Binary Search (Tìm kiếm nhị phân) |
| 3 | O(n log n) | O(n) | Two Pointers (Hai con trỏ) |
Bài học kinh nghiệm
- Bài toán có thể được giải quyết hiệu quả bằng cách sắp xếp các tọa độ và sử dụng kỹ thuật hai con trỏ (Two Pointers) để tìm điểm gần nhất.
- Việc sử dụng
long longlà bắt buộc khi tính toán khoảng cách và lưu trữ giá trị tối thiểu do tọa độ lên tới 10^9 và phép trừ có thể ra giá trị lớn.
Lỗi thường gặp
- Tràn số (Integer Overflow): Nếu dùng
intđể tính toán khoảng cách (ví dụ:abs(b[i] - r[j])), kết quả có thể tràn số nếu chênh lệch lớn hơn 2*10^9. Luôn ép kiểu sanglong long. - Lỗi Logic Hai Con Trỏ: Sai lầm khi không tăng đúng con trỏ (VD: tăng cả hai cùng lúc) dẫn đến bỏ lỡ cặp điểm tối ưu. Logic chuẩn là chỉ dịch chuyển con trỏ có giá trị nhỏ hơn để hy vọng tìm được khoảng cách nhỏ hơn.
Bình luận