Hướng giải của Hoán Vị Nhỏ Nhất Từ Điển

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

Hướng dẫn giải

Để thu được hoán vị nhỏ nhất từ điển với tối đa \(K\) lần đổi chỗ, ta áp dụng thuật toán tham lam kết hợp Fenwick Tree:

  1. Duyệt tìm các phần tử từ nhỏ nhất \(1 \to N\).
  2. Với mỗi giá trị, ta tính số lượng vị trí thực tế của nó đã bị dịch chuyển về phía trước do các phần tử nhỏ hơn đã được nhấc đi trước đó.
  3. Sử dụng Fenwick Tree quản lý các phần tử đã được đưa lên đầu.
  4. Giá trị chênh lệch chỉ số thực tế chính là số phép đổi chỗ kề nhau cần dùng. Nếu chi phí này nhỏ hơn hoặc bằng số lượt \(K\) còn lại, ta thực hiện đổi chỗ (đưa lên đầu), cập nhật \(K\) và cập nhật Fenwick Tree.

Mã nguồn C++ mẫu

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

int n;
vector<int> bit;

void update(int i, int val) {
    for (; i <= n; i += i & -i) bit[i] += val;
}

int query(int i) {
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    long long k;
    if (!(cin >> n >> k)) return 0;
    vector<int> a(n + 1);
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    bit.assign(n + 2, 0);
    vector<int> ans;
    vector<bool> used(n + 1, false);
    for (int val = 1; val <= n; val++) {
        int original_pos = pos[val];
        int shift = query(n) - query(original_pos);
        int current_pos = original_pos + shift;
        long long cost = current_pos - (ans.size() + 1);
        if (cost <= k) {
            k -= cost;
            used[val] = true;
            ans.push_back(val);
            update(original_pos, 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!used[a[i]]) {
            ans.push_back(a[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i == n - 1 ? "" : " ");
    }
    cout << "\n";
}

Nhận xét

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