Đếm cặp trong mảng thỏa i*arr[i] > j*arr[j] trong C++

Cho mảng số. Tìm số cặp (arr[i], arr[j]) thỏa i*arr[i] > j*arr[j] với i < j.

Ví dụ

Đầu vào − arr[] = [1,5,4,1,2,8,3]

Đầu ra − 3

Giải thích − Các cặp: (5,1), (4,1), (8,3).

Đầu vào − arr[] = [-1,-2,3,4,5,6]

Đầu ra − 1

Giải thích − Cặp: (-1,-2).

Phương pháp giải

Duyệt 2 vòng lặp i=0..n-2, j=i+1..n-1. Nếu i*arr[i] > j*arr[j] thì count++.

• Hàm condition_pair(int arr[], int size).
• count = 0.
• Lặp i và j, kiểm tra điều kiện, tăng count.
• Trả về count.

Ví dụ code

#include <iostream>
using namespace std;

int condition_pair(int arr[], int size) {
    int count = 0;
    for (int i = 0; i < size - 1; i++)
        for (int j = i + 1; j < size; j++)
            if (i * arr[i] > j * arr[j]) count++;
    return count;
}

int main() {
    int arr[] = {2, 4, 1, 9, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs in an array that hold i*arr[i] > j*arr[j] are: " << condition_pair(arr, size);
    return 0;
}

Đầu ra

Count of pairs in an array that hold i*arr[i] > j*arr[j] are: 2