Nội dung:
Cho một danh sách chứa các số nguyên không âm, Với mỗi phần tử trong mảng, bạn được quyền tăng thêm cho phần tử đó một giá trị nguyên dương bất kì. Hãy xác định số phép biến đổi ít nhất để mảng trở thành tăng dần (phần tử đứng phía sau lớn hơn phần tử đứng phía trước).
Ví dụ:
- Cho arr = [1, 1], kết quả sẽ là 1. Bạn cần dùng ít nhất 1 phép biến đổi, là tăng số thứ hai thêm 1 đơn vị để thu được mảng tăng dần [1,2]
- Cho arr = [2, 1, 3], kết quả sẽ là 2. Bạn cần dùng ít nhất 2 phép biến đổi:
- Tăng
1
thêm 2
đơn vị, thành số 3
- Tăng
3
thêm 1
đơn vị, thành số 4
Bạn thu được mảng tăng dần [2,3,4]
- Cho arr = [1, 2, 3], kết quả sẽ là 0. Mảng đã cho thoả mãn là mảng tăng dần. Bạn ko cần sử dụng phép biến đổi nào cả
Dữ liệu nhập:
- Số nguyên dương N là số lượng phần tử của mảng. (0 <= N <= 1000).
- N số nguyên không âm a[i] cách nhau bởi khoảng trắng.(0 <= arr[i] <= 3000).
Dữ liệu xuất:
Xác định số phép biến đổi ít nhất để mảng trở thành tăng dần
Ví dụ:
Nhập |
Xuất |
2
1 1
|
1 |
3
2 1 3
|
2 |
3
1 2 3
|
0 |
Xem hướng dẫn cách làm bài