CSES - Stick Divisions

In this problem, we're asked to find the minimum cost to divide a stick with length $x$ into $n$ sticks with given lengths. It helps to work backwards; what if we start with sticks of lengths $d_1,\ldots,d_n$ and merge them into one?

It turns out that this can be solved using Huffman Coding (also see Wikipedia). The algorithm is simple; take the two shortest sticks, merge them into one, and repeat.

If you're wondering why Huffman Coding always produces an optimal solution, see here.

Implementation

As we want to select both shortest sticks and then insert the combined new stick, we will want to have a data structure where we are able to get the smallest value in the collection, remove it and add new values to the collection. The insert and remove operations can be done easily with a priority queue in $\mathcal{O}(\log n)$ time, while retrieving the smallest value takes constant time.

Time Complexity: $\mathcal{O}(n \log n)$

Copy
#include <iostream>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int x, n;
	cin >> x >> n;
	priority_queue<int, vector<int>, greater<int>> PQ;

Copy
import java.io.*;
import java.util.*;

public class StickDivision {
	public static void main(String[] args) throws IOException {
		BufferedReader in =
		    new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());

		// with our algorithm the variable x will not be used at all