1167. Minimum Cost to Connect Sticks

using System;
using System.Collections.Generic;
public class Solution {
    public int ConnectSticks(int[] sticks) {
        int totalCost = 0;
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        
        foreach (int stick in sticks) {
            pq.Enqueue(stick, stick);
        }
        
        while (pq.Count > 1) {
            int stick1 = pq.Dequeue();
            int stick2 = pq.Dequeue();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.Enqueue(cost, cost);
        }
        
        return totalCost;
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ConnectSticks(vector<int>& sticks) {
        int totalCost = 0;
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        
        foreach (int stick in sticks) {
            pq.Enqueue(stick, stick);
        }
        
        while (pq.size() > 1) {
            int stick1 = pq.Dequeue();
            int stick2 = pq.Dequeue();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.Enqueue(cost, cost);
        }
        
        return totalCost;
    }
}

import java.util.PriorityQueue;

class Solution {
    public int connectSticks(int[] sticks) {
        int totalCost = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int stick : sticks) {
            pq.add(stick);
        }
        
        while (pq.size() > 1) {
            int stick1 = pq.poll();
            int stick2 = pq.poll();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.add(cost);
        }
        
        return totalCost;
    }
}

var connectSticks = function(sticks) {
    const pq = new MinPriorityQueue();
    
    for (const stick of sticks) {
        pq.enqueue(stick);
    }
    
    let totalCost = 0;
    
    while (pq.size() > 1) {
        const stick1 = pq.dequeue().element;
        const stick2 = pq.dequeue().element;
        const cost = stick1 + stick2;
        totalCost += cost;
        pq.enqueue(cost);
    }
    
    return totalCost;
};

import (
    "container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func connectSticks(sticks []int) int {
    pq := &MinHeap{}
    heap.Init(pq)
    for _, stick := range sticks {
        heap.Push(pq, stick)
    }

    totalCost := 0
    for pq.Len() > 1 {
        stick1 := heap.Pop(pq).(int)
        stick2 := heap.Pop(pq).(int)
        cost := stick1 + stick2
        totalCost += cost
        heap.Push(pq, cost)
    }

    return totalCost
}

Algorithm

Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4).

Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость.

Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций.

😎