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

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

• 임의의 양의 정수 k를 선택하고

• 임의의 위치를 ​​선택하고 해당 위치에 k를 삽입합니다.

• 이렇게 하면 시퀀스가 ​​변경되고 다음 작업에서 이 시퀀스를 계속합니다.

ul>

조건을 만족하는 데 필요한 최소 피연산자 수를 찾아야 합니다. A[i]

입력이 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].

단계 h2>

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

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

Example

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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

Input

{ 1, 2, 5, 7, 4 }

Output

3

위 내용은 C++ 프로그램: 값보다 작은 인덱스를 가진 요소를 배치하는 데 필요한 작업 수를 계산합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!