인덱스가 값보다 작은 요소를 배치하는 데 필요한 작업 수를 계산하는 C++ 프로그램

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. 이러한 작업은 여러 번 수행할 수 있습니다. −

양의 정수 k를 선택하십시오.
시퀀스에서 임의의 위치를 선택하고 해당 위치에 k를 삽입합니다.
그래서 순서가 바뀌었고 다음 작업에서 이 순서로 진행합니다.

조건을 만족하는 데 필요한 최소 연산 수를 찾아야 합니다. A[i] <=i for all i in range 0 to n-1.

따라서 입력이 A =[1, 2, 5, 7, 4]와 같으면 출력은 3이 됩니다. [1,2,5,7,4] ~ [1]과 같은 작업을 수행할 수 있기 때문입니다. ,2,3,5,7,4] ~ [1,2,3,4,5,7,4] ~ [1,2,3,4,5,3,7,4].

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
}

입력

{ 1, 2, 5, 7, 4 }