Trung bình cộng của phạm vi trong mảng trong C++

Trong bài toán này, chúng ta được cho một mảng n số nguyên và m truy vấn. Nhiệm vụ là tạo một chương trình tính giá trị nguyên (làm tròn xuống) của trung bình cộng các phạm vi do các truy vấn cho.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào –

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

Đầu ra –

7 9

Để giải quyết bài toán này, chúng ta có hai phương pháp: phương pháp trực tiếp và phương pháp sử dụng tiền tố tổng.

Trong phương pháp trực tiếp, với mỗi truy vấn, chúng ta sẽ lặp từ chỉ số bắt đầu đến chỉ số kết thúc của phạm vi. Cộng tất cả các số nguyên của mảng và chia cho số lượng. Phương pháp này hoạt động tốt và in ra kết quả nhưng không hiệu quả.

Sử dụng tiền tố tổng

Trong phương pháp này, chúng ta sẽ tính mảng tiền tố tổng, lưu trữ tổng của tất cả các phần tử của mảng đến chỉ số i. Tức là prefixSum(4) là tổng của tất cả các phần tử đến chỉ số 4.

Bây giờ, sử dụng mảng tiền tố tổng này, chúng ta sẽ tính trung bình cho mỗi truy vấn bằng công thức:

Trung bình = prefixSum[upper] - prefixSum(lower-1) / upper-lower+1

Upper và lower là các chỉ số cho trong truy vấn. Nếu lower = 0, prefixSum(lower-1) = 0.

Ví dụ

Chương trình minh họa hoạt động của giải pháp:

#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<<"Trung bình truy vấn 1: "<<queryMean(1, 4)<<endl;
    cout<<"Trung bình truy vấn 2: "<<queryMean(2, 4)<<endl;
    return 0;
}

Kết quả

Trung bình truy vấn 1: 8
Trung bình truy vấn 2: 9