arrayAscending

Một dãy tăng là dãy mà phân tử sau lớn hơn phần tử trước. Hải có một dãy số nguyên a và số nguyên dương k.

Hải có quyền biến đổi dãy đó, môt lượt biến đổi Hải có quyền cộng vào bất kỳ phần tử nào thêm k đơn vị. Hãy đưa ra số lần biến đổi ít nhất để dãy a trở thành dãy tăng.

Ví dụ:

• Với a = [1,3,2,3] và k = 2, thì arrayAscending(a,k) = 2.
  Giải thích:
  2 phép biến đổi đó là:
  • Tăng a[2] lên 2 đơn vị.
  • Tăng a[3] lên 2 đơn vị.
• Với a =[7,2,10] và k = 3, thì arrayAscending(a,k) = 2.
  Giải thích:
  2 phép biến đổi đó là:
  • Tăng a[1] lên 3 đơn vị.
  • Tăng a[1] lên 3 đơn vị.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] Arrays: Integer: a
  1 ≤ s.size() ≤ 106.
1 ≤ a[i] ≤ 103.
  
  [Đầu vào] Integer: k
  1 ≤ k ≤ 103.

• [Đầu ra] Integer
  Một số nguyên là số bước biến đổi ít nhất để biến đổi dãy a thành dãy tăng.

Tác giả: Phan Đức Hải

Fanpage: CodeLearn.io

Group: Codelearn – Tự học lập trình C#, C++, Java, Python,Basic algorithms.