Làm dãy tăng nghiêm ngặt

Đề bài

Mô tả

Cho dãy số nguyên a1,a2,…,an.

Mỗi thao tác, bạn chọn một chỉ số i bất kỳ rồi tăng hoặc giảm ai đi 1. Mỗi thao tác tốn chi phí 1.

Hãy tìm tổng chi phí nhỏ nhất để dãy trở thành tăng nghiêm ngặt, nghĩa là a1<a2<⋯<an.

Các phần tử sau khi biến đổi là số nguyên tuỳ ý: chúng được phép âm và được phép vượt ra ngoài khoảng giá trị ban đầu.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an.

Dữ liệu ra

Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ràng buộc

  • 1≤n≤105
  • |ai|≤106

Ví dụ

Input Output Giải thích
7
2 1 5 11 5 9 11
9 Đổi dãy thành 0 1 5 6 7 9 11, chi phí 2+0+0+5+2+0+0=9.
3
10 1 1
11 Đổi dãy thành 0 1 2, chi phí 10+0+1=11. Nếu chỉ được phép nâng lên thì phải dùng 10 11 12 với chi phí 21, nên việc hạ phần tử đầu là bắt buộc.
5
5 4 3 2 1
12 Đổi dãy thành 1 2 3 4 5, chi phí 4+2+0+2+4=12.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0