#1457. PARTITION - Chia đoạn

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Lê Minh Hoàng ôn Tại Hải Phòng T11/2020

Cho một thanh gỗ độ dài 𝐿 , người ta cần cắt từ thanh gỗ này 𝑛 thanh gỗ với độ dài 𝑎_1, 𝑎_2, … , 𝑎_𝑛 (phần thừa bỏ đi).

Mỗi lần ta có thể lấy mỗi thanh gỗ cắt thành hai đoạn với tỉ lệ độ dài tùy ý, để cắt một thanh gỗ độ dài 𝑘 thành hai đoạn mất chi phí đúng bằng 𝑘 . Tìm cách cưa với chi phí ít nhất.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương 𝐿, 𝑛\ (𝐿 ≤ 10^9; 𝑛 ≤ 10^5) ;
  • Dòng thứ hai chứa 𝑛 số nguyên dương 𝑎_1, 𝑎_2, … , 𝑎_𝑛\ (∑_{i=1}^𝑛 𝑎_𝑖 ≤ 𝐿) .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là chi phí của cách cưa tìm được.

Ví dụ:

Dữ liệu vào:
8 8
1 1 1 1 1 1 1 1
Dữ liệu ra:
24