Làm Phẳng Dãy Số

Buổi 37 — Convex Hull Trick
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved