Dãy sốHình học
Mô tả
Chị Lan điều phối GrabExpress tại quận Bình Thạnh. Mỗi ngày chị ghi lại danh sách A gồm các mốc thời gian (tính bằng giây) mà tài xế xác nhận đã lấy hàng, và danh sách B gồm các mốc thời gian mà khách hàng xác nhận đã nhận hàng. Chị muốn đánh giá chất lượng vận chuyển bằng cách tìm ra cặp mốc — một mốc lấy hàng từ A và một mốc nhận hàng từ B — có khoảng cách thời gian nhỏ nhất, rồi bình phương khoảng cách đó để làm chỉ số "độ trễ" báo cáo cho đội vận hành.
Nhiệm vụ của bạn: cho hai danh sách số nguyên A và B, hãy tìm giá trị nhỏ nhất của (A[i] - B[j])^2 trên mọi cặp chỉ số i, j hợp lệ.
Đầu vào
- Hai danh sách số nguyên A và B, mỗi danh sách là một mảng các số nguyên.
Đầu ra
- Trả về một số nguyên duy nhất là bình phương chênh lệch nhỏ nhất tìm được.
Ràng buộc
- 1 ≤ độ dài A, độ dài B ≤ 10^5.
- -10^6 ≤ A[i], B[j] ≤ 10^6.
- Đảm bảo bình phương kết quả không vượt quá 10^13, nằm trong phạm vi số nguyên 64-bit.
Ví dụ
Ví dụ 1:
- A = [3, 10, 7], B = [5, 12]
- Sắp xếp A: [3, 7, 10], sắp xếp B: [5, 12].
- Với A[0]=3, giá trị B gần nhất là 5 → (3-5)^2 = 4.
- Với A[1]=7, giá trị B gần nhất là 5 → (7-5)^2 = 4.
- Với A[2]=10, giá trị B gần nhất là 12 → (10-12)^2 = 4.
- Kết quả nhỏ nhất là 4.
Đầu ra: 4