Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Heap & Priority Queue

Minimum Cost to Connect Ropes

Easy · Heap & Priority Queue · Asked at Amazon, Microsoft, Goldman Sachs, TCS, Infosys

Connecting two ropes of lengths x and y costs x + y and gives one rope of length x + y. Print the minimum total cost to connect all the ropes into one.

Input

First line: n. Second line: n space-separated integers.

Output

The minimum cost.

Constraints

Always connect the two shortest ropes (like building a Huffman tree). Use a min-heap and 64-bit sums.

Example 1

Input

4
4 3 2 6

Output

29

Example 2

Input

1
7

Output

0

Hints

  1. A rope that is joined early is counted again in every later join, so short ropes should be joined first.
  2. Repeatedly take the two shortest ropes from a min-heap, add their sum to the cost, and push the new rope back.

Approach

Greedy, the same idea as Huffman coding. Put all lengths in a min-heap. While more than one rope remains, pop the two smallest x, y, add x + y to the cost and push x + y. Long ropes are joined last, so they are counted the fewest times. The total can exceed 2^31 — use 64-bit.

Complexity: O(n log n) time · O(n) space

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }
    long long cost = 0;
    while (pq.size() > 1) {
        long long x = pq.top();
        pq.pop();
        long long y = pq.top();
        pq.pop();
        cost += x + y;
        pq.push(x + y);
    }
    cout << cost << "\n";
    return 0;
}

Python solution

import sys
import heapq

data = list(map(int, sys.stdin.read().split()))
heap = data[1:]
heapq.heapify(heap)
cost = 0
while len(heap) > 1:
    x = heapq.heappop(heap)
    y = heapq.heappop(heap)
    cost += x + y
    heapq.heappush(heap, x + y)
print(cost)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) pq.add(sc.nextLong());
        long cost = 0;
        while (pq.size() > 1) {
            long x = pq.poll(), y = pq.poll();
            cost += x + y;
            pq.add(x + y);
        }
        System.out.println(cost);
    }
}

Solve Minimum Cost to Connect Ropes online · All practice problems