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

例

理解を深めるために、次の実装を見てみましょう。 −

#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

以上がC++ プログラム: 値より小さいインデックスを持つ要素を配置するために必要な操作の数を計算します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。