Đếm cặp chỉ số thỏa mãn điều kiện cho trước trong C++

Chúng ta được cho một mảng hoán vị của N số tự nhiên đầu tiên. Mục tiêu là tìm các cặp chỉ số của phần tử thỏa mãn điều kiện:

Nếu mảng là Arr[], thì i,j là chỉ số, đếm cặp phần tử sao cho Arr[i] + Arr[j] = max(Arr[x]) với i <= x <= j.

Tức là tổng của Arr[i] và Arr[j] bằng phần tử lớn nhất xuất hiện giữa hai đoạn này.

Ví dụ

Đầu vào

Arr[] = { 2, 4, 1, 3, 6, 5 }

Đầu ra

Số cặp chỉ số thỏa mãn điều kiện: 1

Giải thích − Tổng các cặp:

2+4=6, 6 là max nhưng không giữa 2 và 4.

2+1=3, 3 không giữa 2 và 1 và max giữa chúng là 4.

2+3=5, 5 không giữa 2 và 3 và max giữa chúng là 4.

2+6=8, 8 không giữa 2 và 6 và max giữa chúng là 4.

Tương tự:

1+5=6, 6 nằm giữa 1 và 5 và max giữa chúng là 6.

Trong 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

Số cặp chỉ số thỏa mãn điều kiện: 2

Giải thích − Tổng các cặp:

1+5=6, 6 là max nhưng không giữa 1 và 5.

1+4=5, 5 nằm giữa 1 và 4 và max giữa chúng là 5.

2+3=5, 5 nằm giữa 2 và 3 và max giữa chúng là 5.

1+3=4, 4 nằm giữa 1 và 3 nhưng max giữa chúng là 5.

Trong tất cả 2 cặp thỏa mãn điều kiện.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên Arr[] lưu số và size độ dài.
• Hàm countPairs(int A[], int n) nhận mảng và kích thước n, trả về số cặp thỏa mãn điều kiện.
• Biến count lưu giá trị 0 ban đầu cho các cặp như vậy.
• Khởi tạo max1 với phần tử đầu tiên và chỉ số của nó maxindex = 0 để lưu giá trị và chỉ số max tìm thấy cho đến nay.
• Duyệt mảng bằng vòng for.
• Trong vòng for lồng nếu A[j] >= max1 thì cập nhật max1 và chỉ số của nó với j.
• 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ì tăng count vì điều kiện thỏa mãn.
• Sau khi kết thúc cả hai vòng lặp trả về kết quả trong count.

Ví dụ mã nguồn

// CPP implementation of the approach
#include <bits/stdc++.h> 
using namespace std; 

// Hàm trả về số cặp chỉ số yêu cầu
int countPairs(int A[], int n) { 
    // Lưu số lượng yêu cầu
    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++; 
        } 
    } 
    // Trả về số đoạn con
    return count; 
} 

int main() { 
    int Arr[] = {3, 4, 6, 1, 5, 2}; 
    int size = 6; 
    cout << endl << "Số cặp chỉ số thỏa mãn điều kiện: " 
         << countPairs(Arr, size); 
    return 0; 
}

Kết quả

Số cặp chỉ số thỏa mãn điều kiện: 1