インデックスが値よりも小さい要素を配置するために必要な操作の数をカウントするC++プログラム

n個の要素を持つ配列Aがあるとします。これらの操作は何度でも実行できます-

• 任意の正の整数kを選択します

• シーケンス内の任意の位置を選択し、その位置にkを挿入します

• そのため、シーケンスが変更され、次の操作でこのシーケンスに進みます。

条件を満たすために必要な操作の最小数を見つける必要があります：A [i]<=0からn-1の範囲のすべてのiに対して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]。

ステップ

これを解決するには、次の手順に従います-

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 }

出力

3