주어진 양의 정수 배열 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(int arr[], int size) 함수는 arr[ ]을 취하고 하위 배열에 존재하는 요소의 평균이 하위 배열에 존재하지 않는 평균보다 크도록 하위 배열의 개수를 반환합니다.
-
배열 new_arr[size]를 사용하여 이전 인덱스 요소까지 합계를 저장합니다.
-
i=0에서 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 루프가 끝나면 결과로 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;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
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