Làm Phẳng Dãy Số
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho dãy số nguyên $a_1, a_2, \dots, a_N$. Bạn cần biến đổi dãy này thành một dãy số nguyên $b_1, b_2, \dots, b_N$ không giảm ($b_1 \le b_2 \le \dots \le b_N$) sao cho tổng độ lệch $\sum_{i=1}^{N} |a_i - b_i|$ là nhỏ nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($|a_i| \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là giá trị nhỏ nhất của $\sum_{i=1}^{N} |a_i - b_i|$.
Ví dụ
| Input | Output |
|---|---|
| 7 3 2 5 1 2 1 3 |
6 |
Giới hạn
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$
Community Discussion