trang chủ / đề bài / dhbb25_dx05_11_seq

Dãy không giảm

Đề bài

Mô tả

Cho dãy n số nguyên dương a1,a2,…,an. Với mỗi số ai (1≤i≤n) ta có thể thực hiện "không, một hoặc nhiều lần" phép biến đổi "tăng hoặc giảm ai một đơn vị".

Yêu cầu: Hãy tính số phép biến đổi ít nhất để dãy đã cho thành dãy không giảm.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương n.
  • Dòng tiếp theo chứa n số nguyên dương a1,a2,…,an (1≤ai≤10000, i=1..n).

Các số trên một dòng cách nhau bởi dấu cách.

Dữ liệu ra

Một số nguyên duy nhất là số phép biến đổi ít nhất để dãy đã cho thành dãy không giảm.

Ràng buộc

  • 1≤n≤100000; 1≤ai≤10000.
  • Có 17 số test ứng với 17 số điểm có n≤8, ai≤6.
  • Có 17 số test khác ứng với 17 số điểm có n<150.
  • Có 17 số test khác ứng với 17 số điểm có n<5000.
  • Có 17 số test khác ứng với 17 số điểm có n≤5000 và đáp án bài toán tìm được chỉ bằng cách sử dụng phép biến đổi trên một phần tử của dãy số.
  • Có 37 số test khác ứng với 37 số điểm có n≤100000.

Ví dụ

Input Output Giải thích
5
2 6 4 3 2
5 Áp dụng 2 lần phép biến đổi "giảm a2 đi 1 đơn vị", 1 lần "tăng a4 lên 1 đơn vị" và 2 lần "tăng a5 lên 1 đơn vị". Dãy thu được là {2,4,4,4,4}.
5
2 6 6 7 7
0 Dãy đã không giảm.

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