CSES - Stick Divisions | Chia gậy

Xem PDF
Tác giả:
Flower_On_Stone , kitsune , unglinh , SPyofgame , ngpin_04
Dạng bài
Đ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


  • -2
    vanphukhang_0604    10:40 a.m. 19 Tháng 8, 2023 ← chỉnh sửa 2

    CSES - Stick Divisions | Chia gậy

    Bạn có một que gậy với độ dài \(x\) và bạn muốn chia nó thành \(n\) que với độ dài định trước, 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 để chia các que là bao nhiêu?

    Input

    • Dòng đầu tiên chứa hai số nguyên \(x \ (1 \leq x \leq 10^9)\) và \(n \ (1 \leq n \leq 2 \cdot 10^5)\): chiều dài của que ban đầu và số que cần có.
    • Dòng thứ hai chứa \(n\) số nguyên \(d_1, d_2, \ldots, d_n \ (\sum d_i = x)\): chiều dài của mỗi que cần có.

    Output

    • In ra một số nguyên là chi phí tối thiểu của việc chia gậy.

    Example

    Test 1

    Input 
    8 3
2 3 3
    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\).