Chương trình C ++ để đếm số lượng hoạt động cần thiết để đặt các phần tử có chỉ số nhỏ hơn giá trị

Giả sử chúng ta có một mảng A với n phần tử. Chúng tôi có thể thực hiện các thao tác này bất kỳ số lần nào -

• Chọn bất kỳ số nguyên dương k

• Chọn bất kỳ vị trí nào trong chuỗi và chèn k vào vị trí đó

• Vì vậy, trình tự đã được thay đổi, chúng tôi tiếp tục với trình tự này trong hoạt động tiếp theo.

Chúng ta phải tìm số phép toán tối thiểu cần thiết để thỏa mãn điều kiện:A [i] <=i với mọi i trong phạm vi từ 0 đến n-1.

Vì vậy, nếu đầu vào là A =[1, 2, 5, 7, 4], thì đầu ra sẽ là 3, vì chúng ta có thể thực hiện các phép toán như:[1,2,5,7,4] đến [1 , 2,3,5,7,4] đến [1,2,3,4,5,7,4] đến [1,2,3,4,5,3,7,4].

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

maxj := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   maxj := maximum of maxj and (A[i] - i - 1)
return maxj

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   int maxj = 0;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      maxj = max(maxj, A[i] - i - 1);
   }
   return maxj;
}
int main() {
   vector<int> A = { 1, 2, 5, 7, 4 };
   cout << solve(A) << endl;
}

Đầu vào

{ 1, 2, 5, 7, 4 }

Đầu ra

3