CSES - Sliding Cost | Chi phí đoạn tịnh tiến
Xem PDF
Điểm:
1600
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là: với mỗi đoạn con gồm \(k\) phần tử liêp tiếp, từ trái sang phải, tính tổng chi phí tối thiểu để tất cả các phần tử bằng nhau.
Bạn có thể tăng hoặc giảm từng phần tử với chi phí \(x\), trong đó \(x\) là chênh lệch giữa giá trị mới và giá trị ban đầu. Tổng chi phí của đoạn con là tổng của các chi phí tăng hoặc giảm mỗi phần tử trong đó.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): số lượng phần tử của mảng và kích thước của đoạn con.
- Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các phần tử của mảng.
Output
- In ra \(n-k+1\) số: các chi phí.
Constraints
- \(1 \le k \le n \le 2 \cdot 10^5\)
- \(1 \le x_i \le 10^9\)
Example
Sample input
8 3
2 4 3 5 8 1 2 1
Sample output
2 2 5 7 7 1
Bình luận
Mong các bạn góp ý để mình sửa đề cho dễ hiểu hơn. Cá nhân mình thấy mình dịch chưa tốt lắm :')
Có thể dịch dễ hiểu hơn bằng cách thêm từ, đảo vị trí các thành phần trong câu (không bám quá sát vào văn bản gốc).
Đề xuất một cách như sau:
Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là: với mỗi đoạn con gồm \(k\) phần tử liên tiếp, tính tổng chi phí tối thiểu để làm cho tất cả các phần tử bằng nhau.
Bạn có thể tăng hoặc giảm từng phần tử với chi phí \(x\), trong đó \(x\) là chênh lệch giữa giá trị mới và giá trị ban đầu. Tổng chi phí của đoạn là tổng các chi phí tăng / giảm mỗi phần tử trong đó.
Đề xuất tiêu đề những bài Sliding thì nên chuyển thành "đoạn tịnh tiến"
Ví dụ CSES - Sliding Cost | Chi phí đoạn tịnh tiến
Cảm ơn ông, tôi dịch hơi bất cẩn quá 😃