Đếm số mảng con có trung bình lớn hơn trung bình phần tử còn lại trong C++

Cho một mảng arr[] các số nguyên dương. Mục tiêu là tìm số lượng mảng con của arr[] có trung bình các phần tử lớn hơn trung bình của các phần tử còn lại của arr[] không nằm trong mảng con đó.

Ví dụ

Đầu vào

arr[] = { 3, 2, 4 }

Đầu ra

Số mảng con có trung bình lớn hơn phần tử còn lại là: 2

Giải thích

Các mảng con là: [3], [2], [4], [3,2], [2,4], [3,2,4]. Trung bình của [4] là 4 lớn hơn trung bình của [2,3]. Trung bình của [3,2,4] là 3 lớn hơn trung bình của [].

Đầu vào

arr[] = { 3, 3, 3 }

Đầu ra

Số mảng con có trung bình lớn hơn phần tử còn lại là: 1

Giải thích

Các mảng con là: [3], [3], [3], [3,3], [3,3], [3,3,3]. Trung bình của [3,3,3] là 3 lớn hơn trung bình của [].

Phương pháp sử dụng

Trong phương pháp này, tạo một mảng tiền tố prefix_sum[] sẽ lưu tổng các phần tử đến chỉ số i trong prefix_sum[i]. Bây giờ chúng ta có tổng đến phần tử trước đó, sau đó tính tổng đến arr[i] và số lượng phần tử là j-i+1 và tính trung bình.

• Nhận mảng arr[] làm đầu vào.
• Hàm count(int arr[], int size) nhận arr[] và trả về số mảng con mà trung bình phần tử trong mảng con lớn hơn trung bình phần tử không trong mảng con.
• Tạo mảng new_arr[size] để lưu tổng đến chỉ số trước đó.
• Duyệt từ i=0 đến i<size và đặt new_arr[i] với new_arr[i-1] + arr[i-1].
• Bây giờ duyệt new_arr[] bằng hai vòng lặp for.
• Bây giờ tính total_1 là tổng các mảng con trước đó. Và số phần tử trong nó là count_1.
• Tính total_2 là tổng các mảng con tiếp theo và số phần tử trong nó là count_2.
• Tính trung bình: check_1 = total_1 / count_1 và check_2 = total_2 / count_2.
• Nếu trung bình check_1 > check_2 thì tăng biến đếm.
• Cuối cùng của vòng lặp for trả về biến đếm làm kết quả.

Ví dụ mã

#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 << "Số mảng con có trung bình lớn hơn phần tử còn lại là: " << count(arr, size);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số mảng con có trung bình lớn hơn phần tử còn lại là: 6