처음 N개의 자연수의 순열 배열이 제공됩니다. 여기서 목표는 아래에 언급된 조건을 충족하는 요소의 인덱스 쌍을 찾는 것입니다 -
배열이 Arr[]이면 i,j는 인덱스이고 Arr[i]+Arr[j]=max(Arr[x])가 되도록 요소 쌍을 센다. i<=x<=j.
즉, Arr[i]와 A[j]의 합은 두 세그먼트 사이에 발생하는 최대 요소와 같습니다.
입력
Arr[]= { 2,4,1,3,6,5 } 출력
Count of index pairs which satisfy the given condition:1
설명 − 쌍의 합이 주어집니다. −
2+4=6, 6이 최대이지만 2와 4 사이는 아닙니다.
2+1=3, 3은 2와 1 사이가 아니며 그 사이의 최대값은 4입니다.
2+3=5, 5는 2와 3 사이에 있지 않으며 그 사이의 최대값은 4입니다.
2+6=8, 8은 2와 6 사이에 있지 않으며 그 사이의 최대값은 4입니다.
마찬가지로
1+5=6, 6은 1과 5 사이이고 그 사이의 최대값은 6입니다.
조건을 만족하는 쌍은 모두 1쌍만 존재합니다.
입력
Arr[]= { 1,2,5,4,3 } 출력
Count of index pairs which satisfy the given condition:2
설명 − 쌍의 합이 주어집니다. −
1+5=6, 6은 최대값이지만 1과 5 사이는 아닙니다.
1+4=5, 5는 1과 4 사이에 있으며 그 사이의 최대값은 5입니다.
2+3=5, 5는 2와 3 사이이고 그 사이의 최대값은 5입니다.
1+3=4, 4는 1과 3 사이에 있지만 그 사이의 최대값은 5입니다.
2개의 쌍 중 조건을 만족하는 쌍이 모두 존재합니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 Arr[]은 숫자와 길이를 저장합니다.
-
countPairs(int A[],int n) 함수는 배열과 크기 n을 입력으로 받아 위의 조건을 만족하는 쌍의 개수를 반환합니다.
-
변수 개수는 이러한 쌍에 대한 초기 값 0을 저장하는 데 사용됩니다.
-
max1의 첫 번째 요소와 maxindex의 인덱스를 0으로 초기화하여 지금까지 찾은 최대값의 값과 인덱스를 저장합니다.
-
for 루프를 사용하여 배열 탐색을 시작합니다.
-
A[j]>=max1이 주어진 경우 중첩 for 루프 내부에서 max1과 해당 인덱스를 j로 업데이트합니다.
-
A[i] 및 A[j]의 각 쌍에 대해 합계가 max1과 같고 인덱스 maxindex가 i와 j 사이에 있으면 조건이 충족됨에 따라 증분 개수가 됩니다.
-
종료 후 두 루프 모두 count에 있는 결과를 반환합니다.
예시
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the count of
// required index pairs
int countPairs(int A[], int n){
// To store the required count
int count = 0;
int i,j,k;
int max1=A[0];
int maxindex=0;
for ( i = 0; i<n-1; i++){
for(j=i+1;j<n;j++){
if(A[j]>=max1){
max1=A[j];
maxindex=j;
}
if(A[i]+A[j]==max1 && maxindex>=i && maxindex<=j)
count++;
}
}
// Return count of subsegments
return count;
}
int main(){
int Arr[] = {3, 4, 6, 1, 5, 2};
int size =6;
cout <<endl<<"Count of index pairs which satisfy the given condition:"
<<countPairs(Arr,size);
return 0;
} 출력
Count of index pairs which satisfy the given condition:1