Hướng giải của Đếm số cặp nghịch thế

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Để đếm số cặp nghịch thế hiệu quả trong \(O(N \log N)\), ta có thể cải tiến thuật toán Sắp xếp trộn (Merge Sort):

  1. Khi chia đôi mảng thành hai mảng con L (bên trái) và R (bên phải) đã được sắp xếp tăng dần.
  2. Trong quá trình trộn hai mảng con lại với nhau:
    • Nếu phần tử hiện tại của L nhỏ hơn hoặc bằng phần tử hiện tại của R, ta đưa phần tử của L vào mảng kết quả.
    • Nếu phần tử hiện tại R[j] nhỏ hơn phần tử hiện tại L[i], điều này có nghĩa là mọi phần tử từ L[i] đến cuối mảng con trái đều lớn hơn R[j]. Do đó, số lượng cặp nghịch thế được đóng góp bởi R[j] chính là số phần tử còn lại trong mảng con trái L (tức là mid - i + 1). Ta cộng thêm số lượng này vào kết quả.

Độ phức tạp thời gian: \(O(N \log N)\).

Xem code mẫu C++ 
#include <iostream>
#include <vector>
using namespace std;

long long merge_and_count(vector<long long>& a, int left, int mid, int right) {
    vector<long long> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long count = 0;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            count += (mid - i + 1);
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int p = 0; p < k; ++p) {
        a[left + p] = temp[p];
    }
    return count;
}

long long merge_sort_and_count(vector<long long>& a, int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    long long count = 0;
    count += merge_sort_and_count(a, left, mid);
    count += merge_sort_and_count(a, mid + 1, right);
    count += merge_and_count(a, left, mid, right);
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long ans = merge_sort_and_count(a, 0, n - 1);
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.