ค่าเฉลี่ยของช่วงในอาร์เรย์ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม n ตัว และคำถาม m ข้อ งานของเราคือสร้างโปรแกรมที่คำนวณค่าเฉลี่ยแบบจำนวนเต็ม (ปัดลง) ของช่วงที่กำหนดโดยคำถาม

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต -

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

เอาต์พุต -

7 9

ในการแก้ปัญหานี้ เรามีสองวิธี คือ วิธีโดยตรง และวิธีใช้ Prefix Sum

ในวิธีโดยตรง สำหรับแต่ละคำถาม เราจะวนลูปจากดัชนีเริ่มต้นถึงดัชนีสิ้นสุดของช่วง แล้วบวกจำนวนเต็มทั้งหมดในอาร์เรย์และหารด้วยจำนวน วิธีนี้ทำงานได้ดีและพิมพ์ผลลัพธ์ แต่ไม่ใช่วิธีที่มีประสิทธิภาพ

การใช้ Prefix Sum

ในวิธีนี้ เราจะคำนวณอาร์เรย์ Prefix Sum ซึ่งจะเก็บผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์จนถึงดัชนีที่ i คือ prefixSum(4) คือผลรวมขององค์ประกอบทั้งหมดจนถึงดัชนี 4

ตอนนี้ ใช้ Prefix Sum array นี้ เราจะคำนวณค่าเฉลี่ยสำหรับแต่ละคำถามโดยใช้สูตร:

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

Upper และ lower คือดัชนีที่กำหนดในคำถาม ถ้า 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