Tìm độ khác biệt tương thích giữa hai mảng trong C++

Hai người bạn xếp hạng n bộ phim (số 1..n). Độ khác biệt tương thích = số cặp phim mà thứ hạng tương đối khác nhau giữa hai người.

Ví dụ: A=[3,1,2,4,5], B=[3,2,4,1,5]. Phim 1 xếp trước 2 và 4 trong A nhưng sau trong B → 2 cặp không khớp. Kết quả = 2.

Thuật toán

1. Duyệt i từ 0 đến n-1.
2. Nếu A[i] != B[i], tìm vị trí j > i trong B nơi B[j] == A[i].
3. Dịch chuyển B[j] về vị trí i bằng cách hoán đổi liên tiếp với phần tử trước nó, đếm số lần hoán đổi → đó là số cặp nghịch thế mới tạo ra.

Ví dụ minh họa (C++)

#include <iostream>
using namespace std;

int getArrayDiff(int A[], int B[], int n) {
    int diff = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] != B[i]) {
            int j = i + 1;
            while (A[i] != B[j]) ++j;
            while (j != i) {
                swap(B[j], B[j-1]);
                --j;
                ++diff;
            }
        }
    }
    return diff;
}

int main() {
    int A[] = {3, 1, 2, 4, 5};
    int B[] = {3, 2, 4, 1, 5};
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Do khac biet tuong thich: " << getArrayDiff(A, B, n);
    return 0;
}

Kết quả

Do khac biet tuong thich: 2