Đếm số mảng con sao cho giá trị trung bình của các phần tử có trong mảng con lớn hơn số phần tử không có trong mảng con trong C ++

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

Ví dụ

Đầu vào

arr[ ] = { 3, 2, 4 }

Đầu ra

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

Giải thích

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 [ ]

Đầu vào

arr[ ] = { 3, 3, 3 }

Đầu ra

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

Giải thích

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 [ ]

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

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

• Lấy một mảng arr [] làm đầu vào.

• Hàm đếm (int arr [], int size) nhận arr [] và trả về số lượng mảng con sao cho giá trị trung bình của các phần tử có trong mảng con lớn hơn giá trị không có trong mảng con.

• Lấy một mảng new_arr [size] để lưu trữ tổng cho các phần tử chỉ mục trước đó.

• Di chuyển từ i =0 đến i

• Bây giờ đi qua new_arr [] bằng cách sử dụng hai vòng lặp for.

• Bây giờ, hãy tính tổng_1 là tổng của các mảng con trước đó. Và các phần tử trong đó như count_1.

• Tính tổng số_2 dưới dạng tổng của các mảng con tiếp theo và các phần tử trong đó dưới dạng số đếm thứ 2.

• Tính giá trị trung bình dưới dạng check_1 =total_1 / count_1; và kiểm tra_2 =total_2 / count_2;

• Nếu kiểm tra trung bình_1> kiểm tra_2 thì tính gia tăng.

• Kết quả là số lượng trả về ở cuối vòng lặp for.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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