Địa điểm du lịch Dailai nổi tiếng với con đường
Tùng-Trúc. Đó là một con đường dài và thẳng, dọc bên đường người ta trồng rất
nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản
lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất a cây tùng và
có ít nhất b cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được
vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả n cây, không có
hai cây nào ở cùng một vị trí. Cây thứ i ở vị trí có khoảng cách đến vị trí bắt
đầu của con đường là d_i (i = 1, 2, ..., n). Với kinh phí có hạn, Ban quản lý
muốn chọn một đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.
Yêu cầu: Cho a, b và vị trí của n cây. Hãy tìm đoạn
đường có độ dài ngắn nhất mà dọc theo đoạn đường đó có ít nhất a cây tùng và b
cây trúc.
Dữ liệu vào: MINROAD.INP
- Dòng đầu chứa 3 số nguyên dương n, a, b (a + b ≤ n)
- Dòng thứ i trong n dòng tiếp theo mỗi dòng chứa hai
số nguyên dương d_i (d_i ≤ 10^9) trong đó d_i là khoảng cách của cây tính từ vị
trí bắt đầu của con đường, k_i = 1 nếu cây thứ i là cây tùng, k_i = 2 nếu là
cây trúc.
Các số trên cùng một dòng được ghi cách nhau ít nhất
một dấu cách.
Dữ liệu ra: MINROAD.OUT
Ghi ra một số nguyên là độ dài đoạn đường ngắn nhất
tìm được, quy ước ghi số -1 nếu không tồn tại đoạn đường nào thỏa mãn điều kiện
đặt ra.
Giới hạn:
d_i ≤ 10^9.
30% số test có n ≤ 300.
30% số test khác có n ≤ 3 000.
40 % số test còn lại có n ≤ 300 000.
Ví dụ:
MINROAD.INP
|
MINROAD.OUT
|
7 2 2
20 2
30 1
25 1
35 1
60 2
65 2
10 1
|
35
|
Lời giải O(N^3)
Vector nghiệm (x1,x2)
QuickSort(D); //O(NlogN)
isOK(x1, x2); //1
vòng lặp đếm số cây, O(N)
Try; //2
vòng lặp liệt kê, O(N^2)
Độ phức tạp tổng thể:
Số lần thử O(N^2) * Chi phí kiểm tra O(N) = O(N^3)
Lời giải O(N^2)
QuickSort(D); //O(NlogN)
SumK1[i], SumK2[i], "i Î[1,n] //O(N)
isOK(x1, x2); //O(1)
Try; //2
vòng lặp liệt kê, O(N^2)
Độ phức tạp tổng thể:
Số lần thử O(N^2) * Chi phí kiểm tra O(1) = O(N^2)
Lời giải O(NlogN)
Thủ tục Try chỉ cần 1 vòng lặp x2, chi phí của
isOK(x2) là O(logN).
Độ phức tạp tổng thể:
Số lần thử O(N) * Chi phí kiểm tra O(logN) = O(NlogN)
Không có nhận xét nào:
Đăng nhận xét