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!