C++の配列の範囲の平均

この問題では、n個の整数の配列といくつかのm個のクエリが与えられます。私たちの仕事は、クエリによって与えられた範囲の平均の整数値（切り捨て）を計算するプログラムを作成することです。

問題を理解するために例を見てみましょう

入力 −

array = {5, 7, 8, 9, 10}
m = 2; [0, 3], [2, 4]

出力 −

7
9

この問題を解決するために、2つの方法があります。1つは直接で、もう1つはプレフィックス合計を使用します。

直接的なアプローチでは、クエリごとに、範囲の開始インデックスから終了インデックスまでループします。そして、配列のすべての整数を加算し、カウントで除算します。このアプローチは正常に機能し、結果を出力しますが、効果的なアプローチではありません。

prefixSumの使用

このアプローチでは、i番目のインデックスまでの配列のすべての要素の合計を格納するプレフィックス合計配列を計算します。つまり、prefixSum（4）はインデックス4までのすべての要素の合計です。

ここで、このprefixSum配列を使用して、式を使用して各クエリの平均を計算します

Mean = prefixSum[upper] - prefixSum(lower-1) / upper-lower+1

上位と下位は、クエリで指定されたインデックスです。 lower =0の場合、prefixSum（lower-1）=0です。

例

ソリューションの動作を説明するプログラム

#include <iostream>
#define MAX 100
using namespace std;
int prefixSum[MAX];
void initialisePrefixSum(int arr[], int n) {
   prefixSum[0] = arr[0];
   for (int i = 1; i < n; i++)
   prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int queryMean(int l, int r) {
   int mean;
   if (l == 0)
      mean =(prefixSum[r]/(r+1));
   else
      mean =((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1));
      return mean;
}
int main() {
   int arr[] = {5, 7, 8, 9, 10 };
   int n = sizeof(arr) / sizeof(arr[0]);
   initialisePrefixSum(arr, n);
   cout<<"Mean in 1st query: "<<queryMean(1, 4)<<endl;
   cout<<"Mean in 2st query: "<<queryMean(2, 4)<<endl;
   return 0;
}

出力

Mean in 1st query: 8
Mean in 2st query: 9