Trồng cây

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Dọc theo một tuyến phố thẳng có $n$ vị trí kế tiếp nhau để trồng cây đánh số từ $1$ đến $n$ . Hiện tại chỉ có vị trí thứ $k$ ( $1 \leq k \leq n$ ) đã trồng một cây có độ cao là $a_{k}$ , còn các vị trí khác để trống. Theo dự kiến, người ta sẽ trồng cây có độ cao $a_{i}$ tại vị trí thứ $i$ ( $1 \leq i \leq n, i \neq k$ ).

Tuy nhiên, để tăng vẻ đẹp cho hàng cây, người ta muốn tìm một phương án sắp xếp các cây cần trồng vào các vị trí thích hợp (trừ vị trí $k$ ) sao cho tổng tất cả các độ chênh lệch của hai cây trồng liền nhau là nhỏ nhất. Độ chênh lệch của hai cây được trồng tại hai vị trí liền nhau là giá trị tuyệt đối hiệu độ cao của hai cây.

Yêu cầu: Tìm giá trị nhỏ nhất $t$ của tổng tất cả các độ chênh lệch của hai cây trồng liền nhau.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương $n$ và $k$ , $n \leq 10^{3}$ , $1 \leq k \leq n$ .
Dòng sau chứa $n$ số nguyên dương $a_{i}$ , $1 \leq i \leq n$ , là độ cao của cây thứ $i$ theo dự kiến. Mỗi số đều không vượt quá $10^{6}$ .

Dữ liệu ra

Ghi ra số $t$ tìm được.

Ví dụ

Input	Output	Giải thích
5 2 7 3 4 2 6	5	Vị trí $2$ đã trồng cây cao $3$ . Sắp xếp các cây còn lại ( $7, 4, 2, 6$ ) vào các vị trí $1, 3, 4, 5$ sao cho tổng chênh lệch liền kề nhỏ nhất. Một cách tối ưu: $2, 3, 4, 6, 7$ cho tổng $= \| 2 - 3 \| + \| 3 - 4 \| + \| 4 - 6 \| + \| 6 - 7 \| = 1 + 1 + 2 + 1 = 5$ .

Bình luận

Không có bình luận tại thời điểm này.