Nhà kính của Sprout

Điểm: 1,00 (OI)

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

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Giáo sư Pomona Sprout đang chăm sóc khu vườn Thảo Dược Học tại Hogwarts. Dọc theo một lối đi dài trong khu vườn, có $N$ cây thảo dược quý hiếm được trồng tại các vị trí khác nhau trên một đường thẳng. Cây thứ $i$ nằm ở vị trí $x_{i}$ .

Để bảo vệ các cây khỏi thời tiết khắc nghiệt, giáo sư Sprout cần đặt đúng $K$ nhà kính dọc theo lối đi. Mỗi nhà kính có thể được đặt tại bất kỳ vị trí số nguyên nào trên đường thẳng.

Mỗi cây sẽ được bảo vệ bởi nhà kính gần nó nhất. Tuy nhiên, hiệu quả bảo vệ giảm dần theo khoảng cách: chi phí bảo trì cho cây thứ $i$ bằng khoảng cách từ cây đó đến nhà kính gần nhất, tức là $| x_{i} - g |$ với $g$ là vị trí nhà kính gần nhất.

Giáo sư Sprout muốn đặt $K$ nhà kính sao cho tổng chi phí bảo trì của tất cả các cây là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$ — số cây thảo dược và số nhà kính.
Dòng thứ hai chứa $N$ số nguyên $x_{1}, x_{2}, \dots, x_{N}$ — vị trí của các cây trên đường thẳng.

Dữ liệu ra

In ra một số nguyên duy nhất - tổng chi phí bảo trì nhỏ nhất có thể.

Ràng buộc

$1 \leq K \leq N \leq 100 000$
$1 \leq K \leq 300$
$1 \leq x_{i} \leq 10^{9}$
Các vị trí $x_{i}$ không nhất thiết phải phân biệt.

Ví dụ

Input	Output	Giải thích
4 2 1 3 6 10	5	Đặt nhà kính tại vị trí $3$ và $10$ . Cây ở vị trí $1$ có chi phí $‖ 1 - 3 ‖ = 2$ , vị trí $3$ chi phí $0$ , vị trí $6$ chi phí $‖ 6 - 3 ‖ = 3$ , vị trí $10$ chi phí $0$ . Tổng $= 2 + 0 + 3 + 0 = 5$ .
6 3 2 5 8 12 15 20	9	Đặt nhà kính tại vị trí $5$ , $12$ và $20$ . Chi phí: $‖ 2 - 5 ‖ + ‖ 5 - 5 ‖ + ‖ 8 - 5 ‖ + ‖ 12 - 12 ‖ + ‖ 15 - 12 ‖ + ‖ 20 - 20 ‖ = 3 + 0 + 3 + 0 + 3 + 0 = 9$ .

Ghi chú

Nhà kính có thể đặt tại vị trí trùng với cây hoặc không. Vị trí nhà kính phải là số nguyên.

Trong ví dụ 1, ta không thể đạt tổng chi phí nhỏ hơn $5$ . Ví dụ nếu đặt nhà kính tại $2$ và $8$ , tổng chi phí là $| 1 - 2 | + | 3 - 2 | + | 6 - 8 | + | 10 - 8 | = 1 + 1 + 2 + 2 = 6 > 5$ .

Bình luận

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