Trọng số của dãy
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Cho số nguyên dương ~n~ và dãy số nguyên dương ~a_1,a_2,…,a_n~. Trọng số của dãy là chênh lệch lớn nhất giữa hai số liên tiếp nhau trong dãy đó.
Yêu cầu
Có thể thay đổi nhiều nhất ~k~ số trong dãy thành các số nguyên dương bất kì (có thể thay đổi thành các số giống nhau) để trọng số của dãy là nhỏ nhất.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương ~T~ ~(T \le 500)~ cho biết số bộ test.
- Mỗi bộ test được mô tả bằng hai dòng:
- Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 2 \times 10^5)~.
- Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,…,a_n~ ~(1 \le a_i \le 10^9, 1 \le i \le n)~
Tổng ~n~ trong tất cả bộ test không vượt quá ~2 \times 10^5~.
Kết quả
- Với mỗi bộ test, in ra một dòng chứa trọng số nhỏ nhất có thể đạt được với bộ test đó.
Ví dụ
Input
2
6 2
3 1 2 7 6 4
7 4
2 5 7 7 1 8 7
Output
2
0
Giải thích
- Ở bộ test thứ nhất, ta có thể thay đổi số thứ ~4~ có giá trị là ~4~
- Ở bộ test thứ hai, ta có thể đưa thay đổi giá trị của số thứ ~1, 2, 5, 6~ có giá trị là ~7.~
Chấm điểm
- Subtask1 ~(40\%)~: ~1 \le n \le 5000~
- Subtask2 ~(60\%)~: Không có ràng buộc bổ sung
Bình luận
Ta đặt ~m=n-k~ là số phần tử tối thiểu phải giữ nguyên (không đổi). Nếu chọn được một dãy con độ dài ≥ ~m~ sao cho giữa hai phần tử liên tiếp của dãy con luôn có thể “điền” các giá trị vào những vị trí bị đổi để mọi chênh lệch kề nhau không vượt quá ~D~, thì ~D~ là khả thi; ngược lại thì không.
Xét hai vị trí giữ nguyên ~p<q~. Giữa chúng có đúng ~q-p~ bước kề nhau, nên điều kiện cần và đủ để nối từ ~a_p~ đến ~a_q~ với mỗi bước chênh lệch ≤ ~D~ là ~|a_q-a_p|\le (q-p)D~. Tách trị tuyệt đối: ~a_q-a_p\le (q-p)D~ và ~a_p-a_q\le (q-p)D~. Biến đổi tương đương: ~a_p+pD\le a_q+qD~ và ~pD-a_p\le qD-a_q~. Đặt ~U_i=a_i+iD~, ~W_i=iD-a_i~, khi đó điều kiện nối được trở thành ~U_p\le U_q~ và ~W_p\le W_q~.
Với ~D>0~, nếu đồng thời ~U_p\le U_q~ và ~W_p\le W_q~ thì không thể xảy ra ~p>q~ (suy ra hai bất đẳng thức mâu thuẫn), nên thứ tự chỉ số tự động đúng. Vì vậy bài toán kiểm tra ~D~ trở thành: trong tập các điểm ~(U_i,W_i)~, tìm một dãy con không giảm theo cả hai tọa độ có độ dài ≥ ~m~. Cách làm chuẩn là sắp xếp các cặp ~(U,W)~ theo ~U~ tăng, nếu ~U~ bằng nhau thì theo ~W~ tăng; khi đó độ dài dãy con không giảm theo cả hai tọa độ chính là độ dài LNDS (dãy con không giảm dài nhất) của dãy ~W~ sau khi sắp xếp. LNDS tính bằng kỹ thuật “patience sorting”, mỗi phần tử ~w~ đặt vào vị trí
upper_boundtrên mảngtails.Trường hợp ~D=0~ cần tách riêng: khi đó điều kiện nối được giữa hai phần tử giữ nguyên là ~|a_q-a_p|=0~, tức mọi phần tử giữ nguyên phải bằng nhau. Do đó ~D=0~ khả thi khi và chỉ khi tồn tại một giá trị xuất hiện ít nhất ~m~ lần.
Cuối cùng, do tính đơn điệu (nếu ~D~ khả thi thì mọi ~D' > D~ cũng khả thi), ta nhị phân đáp án nhỏ nhất ~D~. Mỗi lần kiểm tra tốn ~O(n\log n)~ (sắp xếp + LNDS), tổng ~O(n\log n\log A)~ với ~A~ cỡ ~10^9~, phù hợp với ~\sum n\le 2\cdot 10^5~.