Khoảng cách nhỏ nhất (RBPOINT2)
Đề bài
Trên trục tọa độ $Ox$ có $n$ điểm xanh và $n$ điểm đỏ. Điểm xanh thứ $i$ có tọa độ $b_i$, điểm đỏ thứ $i$ có tọa độ $r_i$. Với hai điểm có tọa độ $x_1$ và $x_2$, ta định nghĩa khoảng cách giữa hai điểm đó là $|x_2 - x_1|$.
Hãy tìm khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì trong số các điểm đã cho.
Dữ liệu:
- Dòng đầu tiên gồm số nguyên $n$ ($1 \le n \le 10^5$) – số điểm xanh và cũng là số điểm đỏ.
- Dòng thứ hai gồm $n$ số nguyên $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) – với $b_i$ là tọa độ của điểm xanh thứ $i$.
- Dòng thứ ba gồm $n$ số nguyên $r_1, r_2, \ldots, r_n$ ($1 \le r_i \le 10^9$) – với $r_i$ là tọa độ của điểm đỏ thứ $i$. (Ảnh đề gốc ghi nhầm dòng này là "điểm xanh", đúng ra là điểm đỏ.)
Kết quả: in ra khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì.
Chấm điểm:
- Subtask 1 (50% số test): $n \le 1000$.
- Subtask 2 (50% số test): không có giới hạn gì thêm.
1
2
642
1 7
10 52Giải thích:
- Ở ví dụ thứ nhất, khoảng cách giữa điểm xanh duy nhất và điểm đỏ duy nhất là $|2 - 6| = 4$.
- Ở ví dụ thứ hai:
- Khoảng cách giữa điểm xanh thứ 1 và điểm đỏ thứ 1 là $|1 - 10| = 9$.
- Khoảng cách giữa điểm xanh thứ 1 và điểm đỏ thứ 2 là $|1 - 5| = 4$.
- Khoảng cách giữa điểm xanh thứ 2 và điểm đỏ thứ 1 là $|7 - 10| = 3$.
- Khoảng cách giữa điểm xanh thứ 2 và điểm đỏ thứ 2 là $|7 - 5| = 2$.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm thêm đó là toàn bộ tin nhắn của mình với em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇. Bài này các bạn có thể xem đề bài và nộp tại đây nha:
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên LuyenCodeLộ trình lời giải, bấm vào từng phần để nhảy tới:
Hỏi đápEm ấy bắt đầu từ đâu?
Gợi ý cho em: bài đó độ phức tạp tối ưu là $O(N \log N)$.
Có dùng đến sắp xếp và tìm kiếm nhị phân 😉
Cách 1Vét cạn mọi cặp xanh – đỏ: Subtask 1
Cái cách em ấy nghĩ ra đầu tiên thực ra chính là cách dễ nhất: xét mọi cặp (điểm xanh $i$, điểm đỏ $j$), tính $|b_i - r_j|$ rồi lấy nhỏ nhất. Có $n \times n$ cặp nên độ phức tạp là $O(N^2)$.
- Subtask 1: $n \le 1000$ → $10^6$ cặp, chạy trong nháy mắt → ăn được 50% số test.
- Subtask 2: $n = 10^5$ → $10^{10}$ cặp, máy tính 1 giây chỉ lặp được tầm $(3 \text{ đến } 5) \cdot 10^7$ lần → chắc chắn TLE.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n), b(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
cin >> b[i];
}
int Min = INT_MAX;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
Min = min(Min, abs(a[i] - b[j]));
}
}
cout << Min;
return 0;
}n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
Min = float('inf')
for x in a:
for y in b:
Min = min(Min, abs(x - y))
print(Min)Lưu ý: hiệu $|b_i - r_j| \le 10^9 - 1$ vẫn nằm trong kiểu int (tối đa khoảng $2.1 \cdot 10^9$) nên không lo tràn số.
Kiến thứcHàm sort, lower_bound và upper_bound
Trước tiên anh phải nói em hiểu thế này: trong lập trình giải thuật thi đấu hay đi phỏng vấn về giải thuật á, khi em cần giải quyết vấn đề mà cần đến bước sắp xếp, như sắp xếp 1 dãy số tăng dần chẳng hạn, thì chẳng tội gì em phải đi cài đặt 1 thuật toán sắp xếp nào đó như Quick Sort cho dài dòng (nói rõ ra là bản chất Quick Sort cũng chưa tối ưu nữa). Mà em hãy dùng hàm có sẵn đi em, nhanh gọn mà tối ưu.
Hàm sort
Trong C++ em thêm thư viện algorithm (hoặc bits/stdc++.h) rồi gọi sort. Ví dụ có mảng a có n phần tử thì gọi sort(a, a + n); nó sẽ sắp xếp mảng a từ a[0] đến a[n - 1]. Em có thể thử ví dụ thế này:
int a[] = {2, 1, 5, 3, 4, 8, 10, 6, 9, 7};
int n = sizeof(a) / sizeof(a[0]);
sort(a, a + n);
// in ra mảng a: 1 2 3 4 5 6 7 8 9 10Còn nếu gọi sort(a + 2, a + 5); thì nó chỉ sắp xếp từ a[2] đến a[4], tức là nếu in ra thì mảng sẽ là:
Chỉ đoạn a[2..4] (tô xanh) được sắp xếp, phần còn lại giữ nguyên.
Em thử đi nhé, chạy trên máy để ra kết quả cho thấy. Hàm sort này độ phức tạp đảm bảo là $O(N \log N)$, tốt hơn cả mấy thuật toán sắp xếp như Quick Sort hay Merge Sort hay Heap Sort tự cài trong đại đa số trường hợp (trừ những trường hợp rất đặc biệt thì tự cài đặt riêng thuật toán sẽ tốt hơn). Ví dụ Quick Sort thì vẫn có thể bị rơi vào trường hợp xấu, khi đó độ phức tạp sẽ là $O(N^2)$ chứ không phải $O(N \log N)$ đâu.
Thằng sort này nó được cài đặt theo Intro Sort: tùy tình huống có lúc nó dùng Quick Sort, có lúc dùng Heap Sort, có lúc dùng Insertion Sort tùy theo trạng thái dữ liệu, có khi cùng lúc nó làm cả 3. Thành ra dùng thằng này là tối ưu nhất.
lower_bound và upper_bound
Thông thường sau khi sort là áp dụng tìm kiếm nhị phân, thì em hãy tìm hiểu 2 thằng lower_bound và upper_bound, 2 thằng này rất hay ứng dụng đến, như trong bài này là có ứng dụng nó đấy ^^
Ví dụ giờ ta có mảng int a[] = {4, 6, 2, 10, 8}; với n = 5. Gọi sort(a, a + n); thì mảng a được sắp tăng dần thành: 2 4 6 8 10.
Thì lower_bound(vị trí bắt đầu tìm, vị trí kết thúc tìm, x) hiểu đơn giản là: nó trả ra con trỏ trỏ tới phần tử đầu tiên trong đoạn tìm mà phần tử đó $\ge x$. Ví dụ lower_bound(a, a + n, 3) là tìm phần tử đầu tiên trong mảng mà $\ge 3$, đó chính là số 4.
- Vì kết quả là con trỏ nên
cout << lower_bound(a, a + n, 3);chỉ in ra địa chỉ thôi. Muốn lấy giá trị thì dùng toán tử*:cout << *lower_bound(a, a + n, 3);mới in ra 4. - Muốn biết phần tử đó nằm ở index bao nhiêu thì tính khoảng cách từ con trỏ tìm thấy so với con trỏ đầu mảng:
int idx = lower_bound(a, a + n, 3) - a;→idx = 1vìa[1] = 4là phần tử đầu tiên $\ge 3$. Nhớ nhé: phải- ađể nó tính ra index.
Còn upper_bound là trả ra phần tử đầu tiên $> x$ (lớn hơn hẳn). Ví dụ mảng sau khi sắp tăng là 2 4 6 6 6 8 10, có 3 số 6 bị trùng nằm chung 1 chỗ do tính chất sắp tăng dần:
lower_bound(a, a + n, 6) - a = 2 (ô vàng: phần tử đầu tiên $\ge 6$) · upper_bound(a, a + n, 6) - a = 5 (ô tím: a[5] = 8 là phần tử đầu tiên $> 6$).
lower_bound là phần tử đầu tiên $\ge x$; upper_bound là phần tử đầu tiên $> x$. Nếu không có phần tử nào thỏa thì index trả về bằng n (vị trí ngay sau phần tử cuối).Ý tưởngMỗi điểm xanh chỉ cần xét 2 điểm đỏ kề nó
Rồi thì cái bài khoảng cách đó em nhìn nhé: có phải khoảng cách từ 1 điểm xanh đến 1 điểm đỏ chính là trị tuyệt đối hiệu giữa 2 tụi nó đúng không?
Vậy có phải ví dụ nếu điểm xanh có vị trí là 7 đi, thì tưởng tượng trên trục số các điểm đỏ xếp tăng dần, chắc chắn thằng đỏ gần nó nhất sẽ là 1 trong 2 điểm kẹp sát 7 nhất, bao gồm:
- thằng nhỏ nhất thỏa $\ge 7$ (chính là
lower_bound!), - và thằng lớn nhất thỏa $< 7$ (chính là phần tử đứng ngay trước lower_bound),
đúng không? Xét 2 điểm đó, tính khoảng cách từ 7 đến mỗi điểm, để chọn ra Min. Ví dụ danh sách các điểm đỏ là 3 5 6 7 8 9 10 và điểm xanh đang là 7: thằng nhỏ nhất $\ge 7$ là 7, thằng lớn nhất $< 7$ là 6. Khoảng cách $|7 - 7| = 0$, $|7 - 6| = 1$, mà $0 < 1$ nên khoảng cách nhỏ nhất ứng với điểm xanh này là 0.
Mấy điểm đỏ xa hơn (như 3, 5 bên trái hay 8, 9, 10 bên phải) thì chắc chắn xa hơn 2 điểm kẹp kia nên khỏi xét. Em ngẫm nhé, anh nói đến đây là rõ lắm rồi á ^^
Ok đúng, và chọn ra Min của tất cả các Min đó, thì đó là đáp án. Tốt, em cài đặt thử đi.
- Sắp xếp các điểm đỏ tăng dần: $O(N \log N)$.
- Với mỗi điểm xanh $x$:
idx = lower_bound(đỏ, x). Nếuidx != nthì xét đỏ[idx]; nếuidx != 0thì xét đỏ[idx − 1]. Mỗi lần tìm $O(\log N)$. - Đáp án là Min của mọi khoảng cách đã xét.
Minh hoạTìm điểm đỏ gần nhất cho từng điểm xanh
Em nhập tọa độ các điểm xanh, các điểm đỏ (tối đa 10 điểm mỗi màu) rồi bấm Tiếp để xem từng bước: sắp xếp điểm đỏ, rồi với mỗi điểm xanh dùng lower_bound tìm 2 điểm đỏ kẹp nó và cập nhật Min:
Cách 2Sắp xếp + lower_bound – O(N log N)
Source code giải quyết theo tư tưởng anh đã trình bày ở trên, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ đó với em chứ chưa có clean đâu nha. Anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé. Để code ngắn gọn, mảng a là các điểm xanh, mảng b là các điểm đỏ:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n], b[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
cin >> b[i];
}
sort(b, b + n);
int Min = INT_MAX;
for(int i = 0; i < n; ++i){
int idx = lower_bound(b, b + n, a[i]) - b;
if(idx != n){
Min = min(Min, abs(a[i] - b[idx]));
}
if(idx != 0){
Min = min(Min, abs(a[i] - b[idx - 1]));
}
}
cout << Min;
return 0;
}import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()
Min = float('inf')
for i in range(n):
idx = bisect.bisect_left(b, a[i])
if idx != n:
Min = min(Min, abs(a[i] - b[idx]))
if idx != 0:
Min = min(Min, abs(a[i] - b[idx - 1]))
print(Min)Anh nói nhanh 2 chỗ này trong code sợ nếu em chưa biết: if(idx != n) và if(idx != 0).
idx != n: khi tìm vị trí phần tử đầu tiên $\ge x$, nếu lỡ toàn bộ phần tử đều $< x$, chẳng tìm ra được phần tử nào $\ge x$ cả, thì index tính ra sẽ bằng $n$. Nên so sánhidx != nlà để xác nhận có tồn tại phần tử thỏa mãn, tránh truy cậpb[n]ngoài mảng.idx != 0: lỡ như vị trí tìm thấy là 0, nghĩa là chẳng có thằng nào đứng trước đó cả, nếu gọiidx - 1sẽ ra index âm là sai, nên ràng buộc cho kỹ thêm.
if(idx != 0) lỡ bị đặt lồng bên trong if(idx != n). Khi đó nếu mọi điểm đỏ đều nằm bên trái điểm xanh (idx == n) thì điểm đỏ sát bên trái cũng bị bỏ qua luôn. Ví dụ test 1 / 7 / 2 (xanh ở 7, đỏ ở 2) đáp án đúng là 5 nhưng code lồng sẽ in 2147483647. Hệ thống chấm có thể không có test kiểu này nên vẫn được AC, nhưng các bạn nhớ viết 2 câu if tách rời như code ở trên nhé (bản Python thì vốn đã tách đúng).Với $n = 10^5$: sắp xếp tốn khoảng $10^5 \cdot 17 \approx 1.7 \cdot 10^6$ phép so sánh, và $10^5$ lần lower_bound mỗi lần tầm 17 bước → tổng cộng chỉ vài triệu phép tính, chạy rất nhanh.