엄격 증가 수열로 만들기
다이아몬드 III의견: 0
\(N\)개의 정수로 이루어진 수열 \(a_1, a_2, \dots, a_N\)이 있다. 각 원소를 정수 \(b_i\)로 바꿔서 수열 \(b\)가 엄격히 증가(\(b_1 < b_2 < \dots < b_N\))하도록 만들려 한다. \(b_i\)는 음수가 될 수도 있다.
한 원소를 \(a_i\)에서 \(b_i\)로 바꾸는 비용은 \(|a_i - b_i|\)이다. 전체 비용 \(\sum_{i=1}^{N} |a_i - b_i|\) 의 최솟값을 구하여라.
\(1 \le N \le 1{,}000{,}000\)
\(-10^9 \le a_i \le 10^9\)
첫 줄에 수열의 길이 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 공백으로 구분되어 주어진다.
엄격히 증가하는 수열로 만들기 위한 최소 비용을 한 줄에 출력한다.
4
2 1 3 4
2[2,1,3,4]를 엄격 증가로. 예: [1,2,3,4]로 바꾸면 비용 \(|2-1|+|1-2|=2\). 이보다 적은 비용은 불가능하므로 답은 2.
5
5 4 3 2 1
12내림차순 [5,4,3,2,1]. 엄격 증가로 만들려면 예를 들어 [1,2,3,4,5]로 두면 비용 \(4+2+0+2+4=12\). 이것이 최소이다.
riseoj 작성
출처 Original
평가 및 의견
엄격 증가 수열로 만들기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
엄격 증가 수열로 만들기