Mô tả
Tại nhà máy linh kiện ở Bắc Ninh, kỹ sư duy trì hệ thống giao tiếp giữa các bo mạch thông qua các phiên thiết lập cổng. Mỗi phiên có một thời điểm bắt đầu và một thời điểm kết thúc (tính bằng giây). Hệ thống ghi lại log của n phiên như vậy.
Để kiểm tra độ ổn định của phần cứng, kỹ sư muốn đo lường tổng thời gian trống giữa các phiên. Cụ thể, kỹ sư sẽ chia n phiên thành n/2 cặp (mỗi phiên thuộc đúng một cặp). Với mỗi cặp (phiên A, phiên B), thời gian trống được tính là khoảng thời gian từ khi phiên kết thúc sớm hơn bắt đầu cho đến khi phiên kết thúc muộn hơn kết thúc. Nói cách khác, nếu phiên A có (bắt đầu_A, kết_thúc_A) và phiên B có (bắt đầu_B, kết_thúc_B) với kết_thúc_A <= kết_thúc_B, thì thời gian trống của cặp này là kết_thúc_B - kết_thúc_A.
Nhiệm vụ của bạn là tìm cách ghép đôi n phiên thành n/2 cặp sao cho tổng thời gian trống của tất cả các cặp là lớn nhất.
Đầu vào
- Dòng đầu tiên chứa số nguyên chẵn
n(2 ≤ n ≤ 10^5) — số lượng phiên. ndòng tiếp theo, mỗi dòng chứa hai số nguyênsvàt(0 ≤ s < t ≤ 10^9) — thời điểm bắt đầu và kết thúc của một phiên.
Đầu ra
- In ra một số nguyên duy nhất — tổng thời gian trống lớn nhất có thể đạt được.
Ràng buộc
nlà số chẵn, 2 ≤ n ≤ 10^5.- 0 ≤ s < t ≤ 10^9.
- Kết quả đảm bảo nằm trong phạm vi số nguyên 64-bit (|kết quả| ≤ 10^14).
Ví dụ
Ví dụ 1:
Input: 4 1 3 2 6 4 8 5 7
Output: 8
Giải thích: Bốn phiên có thời điểm kết thúc lần lượt là 3, 6, 8, 7. Để tổng trống lớn nhất, ta ghép phiên kết thúc sớm nhất với muộn nhất, và phiên thứ hai từ đầu với thứ hai từ cuối:
- Cặp 1: phiên kết thúc lúc 3 và phiên kết thúc lúc 8 → trống = 8 - 3 = 5.
- Cặp 2: phiên kết thúc lúc 6 và phiên kết thúc lúc 7 → trống = 7 - 6 = 1.
Tổng = 5 + 1 = 6... nhưng chờ đã, hãy thử cách khác. Ghép (3, 7) và (6, 8):
- Cặp 1: 3 và 7 → trống = 4.
- Cặp 2: 6 và 8 → trống = 2.
Tổng = 6. Vậy cách tốt nhất là ghép đầu-cuối theo thứ tự đã sắp xếp: (3,8) và (6,7) cho tổng = 5+1 = 6. Nhưng đáp án đúng là 8.
Thực tế, kỹ thuật tối ưu là: sắp xếp thời điểm kết thúc rồi chia nửa. nửa đầu (nhỏ hơn) ghép với nửa sau (lớn hơn) theo thứ tự: phần tử thứ i nhỏ nhất ghép với phần tử thứ i nhỏ nhất của nửa sau.
Sắp xếp kết thúc: [3, 6, 7, 8]. Nửa đầu: [3, 6], nửa sau: [7, 8]. Ghép: (3,7) và (6,8) → trống = (7-3) + (8-6) = 4 + 2 = 6.
Hãy kiểm tra lại: đáp án đúng cho test này là 6.
Input (sửa lại): 4 1 3 2 8 4 6 5 7
Sắp xếp kết thúc: [3, 6, 7, 8]. Ghép đối xứng: (3,8) và (6,7) → (8-3)+(7-6) = 5+1 = 6. Ghép nửa: (3,7) và (6,8) → (7-3)+(8-6) = 4+2 = 6.
Kết quả: 6.
Output: 6
Ví dụ 2:
Input: 6 1 2 3 5 4 8 6 10 7 9 11 14
Sắp xếp kết thúc: [2, 5, 8, 9, 10, 14]. Ghép đầu-cuối: (2,14), (5,10), (8,9) → (14-2)+(10-5)+(9-8) = 12+5+1 = 18.
Output: 18