Số lượng submit của website có hạn, rất mong các bạn chau chuốt thật kỹ code trước khi submit! Ủng hộ 20.000 (hai mươi ngàn đồng) để chúng tôi duy trì website.

Biến đổi dãy

Đề bài: Sơn rất có hứng thú với dãy số nguyên dương. Một lần biến đổi của Sơn có thể chọn 1 trong 2 phép biến đổi sau:

Giảm một phần tử đi 1 đơn vị.
Tăng tất cả phần tử 1 đơn vị.
Cho một dãy a gồm n số nguyên. Hãy tìm và đưa ra số phép biến đổi để dãy trở thành dãy bao gồm tất cả số nguyên từ 1 đến n.

  • Với a = [0,3,1,3] thì kết quả = 2.
    Giải thích: 2 lần biến đổi đó là:
    • Tăng tất cả phần từ 1 đơn vị: a = [1,4,2,4].
    • Giảm a[1] hoặc a[3] đi 1 đơn vị
      Sau 2 bước trên thì dãy a đã có đầy đủ số nguyên từ 1 đến 4.
  • Với a = [1,2,4], thì kết quả = 1.


Đầu vào: Một dãy a gồm n số nguyên.
Đầu ra: Số phép biến đổi để dãy trở thành dãy bao gồm tất cả số nguyên từ 1 đến n.
Chương trình mong muốn: O(nlogn)

Ví dụ:

input:
4 
0 3 1 3
output:
2
input:
3
1 2 4
output:
1

Bạn chưa đăng nhập? Đăng nhập để Submit ngay!

Add a Comment