นับสับอาร์เรย์ที่ค่าเฉลี่ยมากกว่าส่วนที่เหลือด้วย C++

ได้รับอาร์เรย์ arr[] ของจำนวนเต็มบวก เป้าหมายคือหาจำนวนสับอาร์เรย์ (subarray) ที่มีค่าเฉลี่ยของสมาชิกมากกว่าค่าเฉลี่ยของสมาชิกที่เหลือใน arr[] ที่ไม่อยู่ในสับอาร์เรย์นั้น

ตัวอย่าง

Input

arr[] = { 3, 2, 4 }

Output

Count of number of sub-arrays such that the average of elements present in the sub-array is greater than that do not present in the sub-array are: 2

Explanation

The subarrays are: [ 3 ], [ 2 ], [ 4 ], [ 3,2 ], [ 2,4 ], [ 3,2,4 ]. Average of [ 4 ] is 4 which is more than the average of [ 2,3 ]. Average of [ 3,2,4 ] is 3 which is more than the average of [ ]

Input

arr[] = { 3, 3, 3 }

Output

Count of number of sub-arrays such that the average of elements present in the sub-array is greater than that do not present in the sub-array are: 1

Explanation

The subarrays are: [ 3 ], [ 3 ], [ 3 ], [ 3,3 ], [ 3,3 ], [ 3,3,3 ]. Average of [ 3,3,3 ] is 3 which is more than the average of [ ]

วิธีการที่ใช้ในโปรแกรม

วิธีนี้สร้างอาร์เรย์ prefix sum ที่เก็บผลรวมสมาชิกถึง index i ไว้ที่ new_arr[i] จากนั้นคำนวณผลรวมถึง arr[i] และจำนวนสมาชิกเป็น j-i+1 และคำนวณค่าเฉลี่ย

• รับอาร์เรย์ arr[] เป็นอินพุต
• ฟังก์ชัน count(int arr[], int size) คืนค่าจำนวนสับอาร์เรย์ที่ค่าเฉลี่ยมากกว่าส่วนที่เหลือ
• สร้างอาร์เรย์ new_arr[size] เก็บผลรวมถึง index ก่อนหน้า
• วนลูป i=0 ถึง size ตั้ง new_arr[i] = new_arr[i-1] + arr[i-1]
• วนลูป new_arr[] ด้วยลูปสองชั้น
• คำนวณ total_1 ผลรวมสับอาร์เรย์ก่อนหน้า และ count_1 จำนวนสมาชิก
• คำนวณ total_2 ผลรวมสับอาร์เรย์ถัดไป และ count_2 จำนวนสมาชิก
• คำนวณค่าเฉลี่ย check_1 = total_1 / count_1, check_2 = total_2 / count_2
• ถ้า check_1 > check_2 เพิ่ม count
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int count(int arr[], int size){
    int count = 0;
    int new_size = size + 1;
    int new_arr[new_size] = { 0 };
    for (int i = 1; i < new_size; i++){
        new_arr[i] = new_arr[i - 1] + arr[i - 1];
    }
    for (int i = 1; i < new_size; i++){
        for (int j = i; j < new_size; j++){
            int total_1 = new_arr[j] - new_arr[i - 1];
            int count_1 = j - i + 1;
            int total_2 = new_arr[size] - total_1;
            int count_2 = 0;
            if((size - count_1) == 0){
                count_2 = 1;
            } else {
                count_2 = size - count_1;
            }
            int check_1 = total_1 / count_1;
            int check_2 = total_2 / count_2;
            if (check_1 > check_2){
                count++;
            }
        }
    }
    return count;
}

int main(){
    int arr[] = { 2, 6, 2, 4 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of number of sub-arrays such that the average of elements present in the sub-array is greater than that not present in the sub-array are: " << count(arr, size);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count the number of sub-arrays such that the average of elements present in the subarray is greater than that not present in the sub-array are: 6