CSES - Stick Divisions | Chia gậy
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn có một que gậy với độ dài \(x\) và bạn muốn chia nó thành \(n\) que, tổng độ dài các phần bị chia là \(x\).
Mỗi bước bạn có thể lấy bất kì que nào và chia nó thành hai que. Chi phí của một thao tác như vậy là chiều dài của que bị chia.
Chi phí tối thiểu cần thiết để tạo ra các que là bao nhiêu?
Input
- Dòng đầu vào đầu tiên chứa hai số nguyên \(x\) và \(n\): chiều dài của que và số que trong việc chia.
- Dòng thứ hai chứa \(n\) số nguyên \(d_1, d_2, \ldots, d_n\): chiều dài của mỗi que trong việc chia.
Output
- In một số nguyên: chi phí tối thiểu của việc chia.
Constraints
- \(1 \leq x \leq 10 ^ 9\)
- \(1 \leq n \leq 2 \cdot 10 ^ 5\)
- \(\sum d_i = x\)
Example
Sample input
8 3
2 3 3
Sample output
13
Note
- Giải thích: Trước tiên, bạn chia que có chiều dài \(8\) thành các que có chiều dài \(3\) và \(5\) (chi phí \(8\)). Sau đó, bạn chia que có chiều dài \(5\) thành các que có chiều dài \(2\) và \(3\) (chi phí \(5\)). Tổng chi phí là \(8 + 5 = 13\).
Bình luận
priority_queue ma lam nhe =))
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.