Editorial for ptit029: Ghép xích

Hiểu bài toán

Bài toán yêu cầu tìm tổng thời gian tối thiểu để nối tất cả các dây xích (có độ dài cho trước) thành một dây xích duy nhất. Mỗi lần nối hai dây xích có độ dài a và b lại với nhau sẽ tốn a + b đơn vị thời gian, và tạo ra một dây xích mới có độ dài bằng tổng hai dây cũ. Mục tiêu là minimize tổng thời gian của tất cả các lần nối.

Đây là bài toán kinh điển về Huffman coding hay cây nén nhị phân (optimal merge pattern). Ý tưởng là luôn nối hai dây xích ngắn nhất có thể vào mỗi bước. Bằng cách này, các dây xích dài sẽ được cộng dồn vào cuối cùng, giảm thiểu tổng chi phí (vì các độ dài lớn hơn chỉ được cộng dồn vào tổng chi phí ở các bước sau, tức là xuất hiện ít lần hơn trong tổng thể).

Các cách tiếp cận

Cách Giải thuật Tham lam sử dụng Min-Heap (Priority Queue)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    priority_queue<ll, vector<ll>, greater<ll>> pq;

    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        pq.push(x);
    }

    ll total_cost = 0;
    const ll MOD = 1e9 + 7;

    while (pq.size() > 1) {
        ll first = pq.top(); pq.pop();
        ll second = pq.top(); pq.pop();

        ll combined = first + second;
        // Cộng dồn chi phí. Lưu ý: kết quả truy xuất theo modulo 10^9+7
        // nhưng logic tham lam phải dùng giá trị thực để so sánh
        total_cost = (total_cost + combined) % MOD;

        pq.push(combined);
    }

    cout << total_cost;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là cách tiếp cận tối ưu và chuẩn nhất cho bài toán này.

1. Khởi tạo Min-Heap: Đưa tất cả độ dài các dây xích vào một Min-Heap (Priority Queue).
2. Lặp: Trong khi số lượng dây xích lớn hơn 1:
   • Lấy ra hai dây xích ngắn nhất (top của heap).
   • Nối chúng lại, chi phí cho lần nối này là tổng của hai độ dài đó.
   • Cộng chi phí này vào tổng thời gian.
   • Đưa độ dài mới (tổng của hai dây cũ) vào heap.
3. Kiểu dữ liệu: Do độ dài dây xích và tổng thời gian có thể rất lớn (lên tới hàng chục tỷ hoặc hơn), cần sử dụng kiểu long long.
4. Modulo: Đề bài yêu cầu in kết quả theo modulo 10^9+7. Ta có thể cộng dồn kết quả theo modulo ngay trong quá trình tính toán để tránh tràn số, nhưng giá trị combined để push vào heap phải là giá trị thực (không mod) để đảm bảo logic tham lam đúng (vì ta cần so sánh độ dài thực của các dây).

Cách Sắp xếp mảng và mô phỏng (ít hiệu quả)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    ll total_cost = 0;
    const ll MOD = 1e9 + 7;

    // Duyệt từ đầu, coi như 2 phần tử đầu luôn là nhỏ nhất
    // Tuy nhiên, khi chèn phần tử mới vào, ta cần sắp xếp lại.
    // Cách này không hiệu quả O(N^2 log N) nếu chèn lại vào vector.
    // Giả sử ta dùng multiset (tương tự heap).
    // Code minh họa cho cách dùng multiset (tương tự heap nhưng code khác)
    // Hoặc nếu chỉ dùng mảng, ta phải dùng Min-Heap cho hiệu quả.
    // Code sau là cách dùng Min-Heap (tương tự Approach 1 nhưng thay vì dùng PQ của thư viện, tự build logic).
    // Để minh họa khác biệt, code này sẽ là cách dùng Multiset để rõ ràng thao tác xóa chèn.

    multiset<ll> ms(a.begin(), a.end());
    while (ms.size() > 1) {
        auto it1 = ms.begin();
        ll first = *it1;
        ms.erase(it1);

        auto it2 = ms.begin();
        ll second = *it2;
        ms.erase(it2);

        ll combined = first + second;
        total_cost = (total_cost + combined) % MOD;
        ms.insert(combined);
    }

    cout << total_cost;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Cách tiếp cận này sử dụng multiset hoặc priority_queue. Nếu dùng mảng thường và sắp xếp lại sau mỗi lần nối, độ phức tạp sẽ rất cao O(N^2 log N) hoặc O(N^2).

Phân tích chi tiết:

• multiset trong C++ là một cấu trúc dữ liệu cây đỏ-đen, tự động sắp xếp tăng dần.
• Thao tác begin() để lấy phần tử nhỏ nhất: O(1).
• Thao tác erase(iterator) và insert(value): O(log N).
• Quá trình lặp N-1 lần cho tổng độ phức tạp O(N log N).

Đây về cơ bản là cách làm tương tự Min-Heap, chỉ khác về mặt cấu trúc dữ liệu.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán tối ưu hóa quy trình nối (Optimal Merge Pattern) có lời giải tham lam: luôn chọn hai phần tử nhỏ nhất để ghép.
• Độ dài các dây xích có thể rất lớn, nhưng tổng chi phí chỉ cần in ra theo modulo. Tuy nhiên, các phép so sánh để tìm ra dây xích ngắn nhất phải dựa trên giá trị thực.

Lỗi thường gặp

• Tràn số (Overflow) nếu dùng biến 32-bit. Phải dùng long long (64-bit).
• Sai logic tham lam: không được nối các dây dài trước.
• Lỗi nhập xuất: cần đọc n số nguyên.