Đếm cặp (p, q) sao cho p xuất hiện ít nhất q lần và q xuất hiện ít nhất p lần trong C++

Cho mảng số nguyên dương. Tìm số cặp (p, q) trong đó p xuất hiện ≥ q lần và q xuất hiện ≥ p lần.

Ví dụ

Đầu vào − arr[] = {3, 3, 3, 5, 5, 6, 6}

Đầu ra − 1

Giải thích − Cặp hợp lệ: (3,3) vì 3 xuất hiện 3 lần.

Đầu vào − arr[] = {3, 3, 3, 3, 3, 5, 5, 5, 6, 6}

Đầu ra − 3

Giải thích − Các cặp: (3,3), (5,5), (3,5) (3 xuất hiện 5 lần, 5 xuất hiện 3 lần).

Phương pháp giải

• Dùng unordered_map đếm tần suất, vector lưu các giá trị duy nhất.
• Duyệt vector các giá trị duy nhất vec[i]:
  • Nếu freq[vec[i]] < vec[i] → bỏ qua.
  • Nếu freq == vec[i] → count++.
  • Nếu freq > vec[i] → count++ (cặp (vec[i], vec[i])) + duyệt j từ vec[i]+1 đến freq[vec[i]], nếu freq[j] >= vec[i] thì count++.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

int pair_count(int arr[], int len) {
    int count = 0;
    vector<int> vec;
    unordered_map<int, int> um;
    for (int i = 0; i < len; i++) {
        um[arr[i]]++;
        if (um[arr[i]] == 1) vec.push_back(arr[i]);
    }
    for (int i = 0; i < vec.size(); i++) {
        if (um[vec[i]] < vec[i]) continue;
        else if (um[vec[i]] == vec[i]) count++;
        else {
            count++;
            for (int j = vec[i] + 1; j <= um[vec[i]]; j++) {
                if (um[j] >= vec[i]) count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 1, 1, 5, 5, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: " << pair_count(arr, size);
    return 0;
}

Đầu ra

Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1