计算子数组的数量,以使子数组中存在的元素的平均值大于C ++中子数组中不存在的元素的平均值
给定正整数的数组arr[]。目的是找到arr[]子数组的计数,这些子数组的元素平均值大于其中不存在的arr[]其余元素的平均值。
例如
输入值
arr[ ] = { 3, 2, 4 }输出结果
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
说明
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 [ ]
输入值
arr[ ] = { 3, 3, 3 }输出结果
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
说明
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 [ ]
以下程序中使用的方法如下-
在此方法中,创建一个前缀和数组,该数组将在new_arr[i]中存储直到索引i的元素之和。现在我们有了到前一个元素的总和,然后计算了到arr[i]的总和,元素数为j-i+1并计算了平均值。
以数组arr[]作为输入。
函数count(intarr[],intsize)取arr[]并返回子数组的计数,以使子数组中存在的元素的平均值大于子数组中不存在的元素的平均值。
取一个数组new_arr[size]来存储总和直到前一个索引元素。
从i=0遍历到i<size,并用new_arr[i-1]+arr[i-1]设置new_arr[i]。
现在使用两个for循环遍历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,则增加计数。
在for循环结束时,返回计数作为结果。
示例
#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; }输出结果
如果我们运行上面的代码,它将生成以下输出-
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