サブ配列に存在する要素の平均がC++のサブ配列に存在しない要素の平均よりも大きくなるように、サブ配列の数を数えます。

正の整数の配列arr[]が与えられます。目標は、要素の平均が、そこに存在しないarr[]の残りの要素の平均よりも大きいarr[]のサブ配列の数を見つけることです。

例

入力

arr[ ] = { 3, 2, 4 }

出力

Count of number of sub-arrays such that the average of elements present in
the sub−array is greater than that do not present in the sub−array are: 2

説明

The subarrays are −
[ 3 ], [ 2 ], [ 4 ], [ 3,2 ], [ 2,4 ], [ 3,2,4 ].
Average of [ 4 ] is 4 which is more than the average of [ 2,3 ].
Average of [ 3,2,4 ] is 3 which is more than the average of [ ]

入力

arr[ ] = { 3, 3, 3 }

出力

Count of number of sub−arrays such that the average of elements present in
the sub−array is greater than that do not present in the sub−array are: 1

説明

The subarrays are −
[ 3 ], [ 3 ], [ 3 ], [ 3,3 ], [ 3,3 ], [ 3,3,3 ].
Average of [ 3,3,3 ] is 3 which is more than the average of [ ]

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

このアプローチでは、インデックスiまでの要素の合計をnew_arr[i]に格納するプレフィックス合計配列を作成します。これで、前の要素までの合計が得られ、次にarr [i]までの合計と要素の数をj−i + 1として計算し、平均を計算します。

• 配列arr[]を入力として受け取ります。

• 関数count（int arr []、int size）はarr []を取り、サブ配列に存在する要素の平均がサブ配列に存在しない要素の平均よりも大きくなるように、サブ配列の数を返します。

  >

• 配列new_arr[size]を取得して、前のインデックス要素までの合計を格納します。

• i =0からi

• 次に、2つのforループを使用してnew_arr[]をトラバースします。

• 次に、total_1を前のサブ配列の合計として計算します。そして、その中の要素はcount_1です。

• total_2を次のサブ配列の合計として計算し、その中の要素をcount_2として計算します。

• 平均をcheck_1=total_1/count_1;として計算します。およびcheck_2=total_2 / count_2;

• 平均check_1>check_2の場合、カウントをインクリメントします。

• forループの最後に、結果としてカウントが返されます。

例

#include <bits/stdc++.h>
using namespace std;
int count(int arr[], int size){
   int count = 0;
   int new_size = size + 1;
   int new_arr[new_size] = { 0 };
   for (int i = 1; i < new_size; i++){
      new_arr[i] = new_arr[i − 1] + arr[i − 1];
   }
   for (int i = 1; i < new_size; i++){
      for (int j = i; j < new_size; j++){
         int total_1 = new_arr[j] − new_arr[i − 1];
         int count_1 = j − i + 1;
         int total_2 = new_arr[size] − total_1;
         int count_2 = 0;
         if((size − count_1) == 0){
            count_2 = 1;
         } else {
            count_2 = size − count_1;
         }
         int check_1 = total_1 / count_1;
         int check_2 = total_2 / count_2;
         if (check_1 > check_2){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 2, 6, 2, 4 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of number of sub−arrays such that the average of elements present in
   the sub−array "<< "is greater than that not present in the sub−array are: "<<count(arr, size);
   return 0;
}

出力

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

Count the number of sub−arrays such that the average of elements present in the subarrayis greater than that not present in the sub-array are: 6