Đếm số cặp nghịch thế dùng Set trong C++ STL

Số cặp nghịch thế (inversion count) đo lường mức độ gần với mảng đã sắp xếp. Mảng đã sắp xếp có inversion count = 0.

Ví dụ

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

int get_Icount(int arr[], int n) {
    multiset<int> set1;
    set1.insert(arr[0]);
    int invcount = 0;
    multiset<int>::iterator itset1;
    for (int i = 1; i < n; i++) {
        set1.insert(arr[i]);
        itset1 = set1.upper_bound(arr[i]);
        invcount += distance(itset1, set1.end());
    }
    return invcount;
}

int main() {
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr)/sizeof(int);
    cout << "Number of inversions count are : " << get_Icount(arr, n);
    return 0;
}

Đầu ra

Number of inversions count are : 6