C++에서 배열의 범위 평균

이 문제에서는 n개의 정수 배열과 m개의 쿼리가 제공됩니다. 우리의 임무는 쿼리에 의해 주어진 범위의 평균의 적분 값(내림)을 계산하는 프로그램을 만드는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 -

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

출력 -

7
9

이 문제를 해결하기 위해 두 가지 방법이 있습니다. 하나는 직접이고 다른 하나는 접두사 합계를 사용하는 것입니다.

직접 접근 방식에서는 각 쿼리에 대해 범위의 시작 인덱스에서 끝 인덱스까지 반복합니다. 그리고 배열의 모든 정수를 더하고 개수로 나눕니다. 이 접근 방식은 잘 작동하고 결과를 인쇄하지만 효과적인 것은 아닙니다.

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