C++で特定の配列を構築するためのサフィックスインクリメント/デクリメント操作の数

正の整数を含むターゲット配列arr[]が与えられます。目標は、すべて0の初期配列を使用してターゲット配列arr[]を構築することです。すべて0の特定の空の配列に適用できる操作は、インクリメント/デクリメント操作の接尾辞になります。

iなどのインデックスを選択すると、サフィックスインクリメント操作の場合、インデックスiから最後のインデックスまでのすべての要素に1が追加されます。

サフィックスデクリメント操作の場合、インデックスiから最後のインデックスまでのすべての要素から1を減算します。

例を挙げて理解しましょう

入力 − arr [] ={1,2,3}

出力 −特定の配列を構築するための接尾辞のインクリメント/デクリメント操作の数は− 3

説明

Starting from { 0, 0, 0 }
Choose index 0, applying suffix increment { 1, 1, 1 }
Choose index 1, applying suffix increment { 1, 2, 2 }
Choose index 2, applying suffix increment { 1, 2, 3 }
Total operations =3

入力 − arr [] ={1、4、5、3}

出力 −特定の配列を構築するための接尾辞のインクリメント/デクリメント操作の数は− 7

説明

Starting from { 0, 0, 0, 0 }
Choose index 0, applying suffix increment { 1, 1, 1, 1 }
Choose index 1, applying suffix increment { 1, 2, 2, 2 }
Choose index 1, applying suffix increment { 1, 3, 3, 3 }
Choose index 1, applying suffix increment { 1, 4, 4, 4 }
Choose index 2, applying suffix increment { 1, 4, 5, 5 }
Choose index 3, applying suffix decrement { 1, 4, 5, 4 }
Choose index 3, applying suffix decrement { 1, 4, 5, 3 }
Total operations = 7

以下のプログラムで使用されているアプローチは次のとおりです

初期配列をB[]とすると。最初の要素B[0]をarr[0]と等しくするため。 arr[0]個のサフィックスインクリメント操作が必要になります。この後、すべてのB [0] =B [1] .... =B [n-1] =arr[0]は等しくなります。

2番目の要素B[1]をarr[1]と等しくするには、|が必要です。 arr [1]-arr [0] |操作の数。 （インクリメントまたはデクリメント）。

したがって、B[i]をarr[i]と等しくするには、|が必要になります。 arr [i]-arr [i-1] |操作の数。

操作の総数は次のようになります| arr [0] | + | arr [1]-arr [0] | +…。 + | arr [n-1] -arr[n-2]|。

• ターゲット配列をarr[]として取得します。

• 関数incr_decr_op（int arr []、int size）は、配列とその長さを受け取り、指定された配列を構築するためのサフィックスのインクリメント/デクリメント操作のカウントを返します

• 初期カウントを0とします。

• forループを使用して配列arr[]をトラバースします

• インデックス0の場合、カウントにarr[i]を追加します。

• 他のインデックスの場合は、abs（arr [i] -arr [i-1]）を追加してカウントします。

• 結果としてのforループリターンカウントの終了時。

例

#include <bits/stdc++.h>
using namespace std;
int incr_decr_op(int arr[], int size){
   int count = 0;
   for (int i = 0; i < size; i++){
      if (i > 0){
         count += abs(arr[i] - arr[i - 1]);
      }
      else{
         count = count + abs(arr[i]);
      }
   }
   return count;
}
int main(){
   int arr[] = { 3, 3, 1, 2, 2 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of suffix increment/decrement operations to construct a given array are: "<<incr_decr_op(arr, size) << endl;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of suffix increment/decrement operations to construct a given array are: 6