Join ropes into one for the lowest total cost, always joining the two shortest first.
What to build
A min-heap that repeatedly gives back the two smallest numbers.
Requirements
- Joining two ropes costs the sum of their lengths, and makes one rope of that length.
- Always join the two shortest ropes that are left.
- Print the total cost of joining all the ropes into one. One rope alone costs 0.
Input
The first line has n. The second line has the n lengths.
Output
The total cost.
Constraints
1 ≤ n ≤ 1000, and each length is from 1 to 1000.
Example
Input:
4
4 3 2 6
Output:
29
Why it works
A rope that is joined early is paid for again in every later join, so the shortest ropes should go first. A heap finds the two shortest in O(log n) each time, where a plain array would need a full search.
Examples
Example 1 · Input
4 4 3 2 6
Expected output
29
Example 2 · Input
1 10
Expected output
0
Hints
Hint 1
Put every length into a min-heap.
Hint 2
While more than one rope is left, pop the two shortest, add their lengths to the total cost, and push the joined rope back.
Hint 3
Write push with a sift-up and pop with a sift-down, as in the lesson.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int heap[1000];
int size = 0;
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void push(int x) {
int i = size++;
heap[i] = x;
while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
swap(&heap[(i - 1) / 2], &heap[i]);
i = (i - 1) / 2;
}
}
int pop(void) {
int top = heap[0];
heap[0] = heap[--size];
int i = 0;
while (1) {
int l = 2 * i + 1, r = 2 * i + 2, smallest = i;
if (l < size && heap[l] < heap[smallest]) smallest = l;
if (r < size && heap[r] < heap[smallest]) smallest = r;
if (smallest == i) break;
swap(&heap[i], &heap[smallest]);
i = smallest;
}
return top;
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
push(x);
}
int cost = 0;
while (size > 1) {
int a = pop();
int b = pop();
cost += a + b;
push(a + b);
}
printf("%d\n", cost);
return 0;
}