DSA03010

Dạng bài

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(N\) sợi dây với độ dài khác nhau được lưu trong mảng \(A\). Nhiệm vụ của bạn là nối \(N\) sợi dây thành một sợi sao cho tổng chi phí nối dây là nhỏ nhất. Biết chi phí nối sợi dây thứ \(i\) và sợi dây thứ \(j\) là tổng độ dài hai sợi dây \(A_i\) và \(A_j\).

Input

Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai dòng:
- Dòng thứ nhất đưa vào số lượng sợi dây \(N\) (\(1 \leq N \leq 10^6\));
- Dòng tiếp theo đưa vào \(N\) số \(A_i\) (\(1 \leq i \leq N, 0 \leq A_i \leq 10^6\)) là độ dài của các sợi dây;
Các số được viết cách nhau một vài khoảng trống.

Output

Đưa ra kết quả mỗi test theo từng dòng.

Example

Test 1

Input

Output

29
62

Bình luận

C0d3

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

long long minCostToConnectRopes(vector<int>& ropes) {
    priority_queue<long long, vector<long long>, greater<long long>> pq; 
    for (int rope : ropes) {
        pq.push(rope);
    }
    long long totalCost = 0;
    while (pq.size() > 1) {
        long long min1 = pq.top();
        pq.pop();
        long long min2 = pq.top();
        pq.pop();

        long long cost = min1 + min2;
        totalCost += cost;
        pq.push(cost);
    }
    return totalCost;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> ropes(n);
        for (int i = 0; i < n; ++i) {
            cin >> ropes[i];
        }
        long long minCost = minCostToConnectRopes(ropes);
        cout << minCost << endl;
    }
    return 0;
}

1 phản hồi