Chi phí nhỏ nhất nối que trong C++

Cho các que độ dài nguyên dương. Nối 2 que độ dài X, Y tốn chi phí X+Y. Lặp cho đến khi còn 1 que. Tìm chi phí nhỏ nhất.

Ví dụ: [2,4,3] → Kết quả: 14 (2+3=5, 5+4=9, tổng=14).

Giải thuật (Min-Heap / Huffman)

1. Min-heap pq chứa tất cả độ dài.
2. Khi pq.size() > 1:
3. Lấy 2 phần tử nhỏ nhất, cộng lại, thêm chi phí vào ans, push tổng vào pq.
4. Trả về ans.

Ví dụ C++

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

class Solution {
public:
    int connectSticks(vector<int>& s) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int x : s) pq.push(x);
        int ans = 0;
        while(pq.size() > 1) {
            int temp = pq.top(); pq.pop();
            temp += pq.top(); pq.pop();
            ans += temp;
            pq.push(temp);
        }
        return ans;
    }
};

int main() {
    vector<int> v = {2,4,3};
    Solution ob;
    cout << ob.connectSticks(v);
    return 0;
}

Đầu vào

[2,4,3]

Đầu ra

14