Chăn Bò Tối Ưu (Silver)

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Có $N$ con bò trốn thoát đứng tại các vị trí phân biệt trên một đường thẳng. Bắt đầu từ vị trí $0$ , bạn cần đến thăm tất cả các con bò để bắt chúng về. Mỗi giây một con bò chưa bị bắt gây ra 1 đồng thiệt hại. Bạn di chuyển với tốc độ 1 đơn vị/giây và bắt bò tức thời khi đến nơi.

Tìm thứ tự thăm các con bò để tổng thiệt hại là nhỏ nhất.

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp theo: Vị trí $P_{i}$ của từng con bò

Dữ liệu ra

Một số nguyên: tổng thiệt hại tối thiểu.

Ràng buộc

$1 \leq N \leq 1000$
$- 500000 \leq P_{i} \leq 500000$
$P_{i} \neq 0$ , tất cả vị trí phân biệt

Ví dụ

Input	Output	Giải thích
4 -2 -12 3 7	20	Thứ tự tối ưu: -2, 3, 7, -12. Di chuyển lần lượt 2, 5, 4, 19 đơn vị, với 3, 2, 1, 0 con bò còn lại tương ứng. Thiệt hại: 2×3 + 5×2 + 4×1 + 19×0 = 6 + 10 + 4 + 0 = 20.

Bình luận

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