Chúng ta được cung cấp một mảng hoán vị của N số tự nhiên đầu tiên. Mục tiêu ở đây là tìm các cặp phần tử trong chỉ mục thỏa mãn điều kiện được đề cập bên dưới -
Nếu một mảng là Arr [] thì i, j là các chỉ số, đếm các cặp phần tử sao cho Arr [i] + Arr [j] =max (Arr [x]) sao cho i <=x <=j.
Nghĩa là, tổng của Arr [i] và A [j] bằng phần tử lớn nhất xảy ra giữa hai phân đoạn.
Đầu vào
Arr[]= { 2,4,1,3,6,5 } Đầu ra
Count of index pairs which satisfy the given condition:1
Giải thích - Tổng các cặp được cho -
2 + 4 =6, 6 là tối đa nhưng không nằm trong khoảng từ 2 đến 4.
2 + 1 =3, 3 không nằm giữa 2 và 1 và tối đa giữa chúng là 4.
2 + 3 =5, 5 không nằm giữa 2 và 3 và tối đa giữa chúng là 4.
2 + 6 =8, 8 không nằm trong khoảng từ 2 đến 6 và tối đa giữa chúng là 4.
Tương tự
1 + 5 =6, 6 nằm trong khoảng từ 1 đến 5 và tối đa giữa chúng là 6.
Trong số tất cả, chỉ có 1 cặp thỏa mãn điều kiện.
Đầu vào
Arr[]= { 1,2,5,4,3 } Đầu ra
Count of index pairs which satisfy the given condition:2
Giải thích - Tổng các cặp được cho -
1 + 5 =6, 6 là tối đa nhưng không nằm trong khoảng từ 1 đến 5.
1 + 4 =5, 5 nằm trong khoảng từ 1 đến 4 và tối đa giữa chúng là 5.
2 + 3 =5, 5 nằm trong khoảng từ 2 đến 3 và tối đa giữa chúng là 5.
1 + 3 =4, 4 nằm trong khoảng từ 1 đến 3 nhưng tối đa giữa chúng là 5.
Có tất cả 2 cặp thỏa mãn điều kiện.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Mảng số nguyên Arr [] lưu trữ các số và kích thước chiều dài của nó.
-
Hàm countPairs (int A [], int n) nhận một mảng và kích thước n của nó làm đầu vào và trả về số lượng các cặp thỏa mãn điều kiện trên ..
-
Số lượng biến được sử dụng để lưu trữ giá trị ban đầu 0 cho các cặp như vậy.
-
Khởi tạo max1 với phần tử đầu tiên và chỉ mục của nó trong maxindex là 0 để lưu trữ chỉ số giá trị của giá trị lớn nhất được tìm thấy cho đến nay.
-
Bắt đầu duyệt qua mảng bằng vòng lặp for.
-
Bên trong vòng lặp for lồng nhau nếu A [j]> =max1 thì cập nhật max1 và chỉ mục của nó bằng j.
-
Đối với mỗi cặp A [i] và A [j] nếu tổng bằng max1 và chỉ số maxindex nằm giữa i và j, thì số gia tăng khi điều kiện được thỏa mãn.
-
Sau khi kết thúc cả hai vòng đều trả về kết quả được đếm.
Ví dụ
// 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;
} Đầu ra
Count of index pairs which satisfy the given condition:1