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

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

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

ป้อนข้อมูล −

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

ผลผลิต −

7
9

ในการแก้ปัญหานี้ เรามี 2 วิธี วิธีแรกใช้โดยตรงและอีกวิธีใช้ผลรวมนำหน้า

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

การใช้คำนำหน้าSum

ในแนวทางนี้ เราจะคำนวณ prefix sum array ซึ่งจะเก็บผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์จนถึงดัชนี ith เช่น prefixSum(4) คือผลรวมขององค์ประกอบทั้งหมดจนถึงดัชนี 4

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

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

ด้านบนและด้านล่างคือดัชนีที่ระบุในแบบสอบถาม ถ้าต่ำกว่า =0, คำนำหน้าSum(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