P1334 {{Ruirui's Wooden Boards}}

{{Ruirui wants to repair the fence around his small pasture by himself.}}

{{He measured the fence and found that he needs $n$ wooden boards, each with an integer length $l_i$. So, he bought one board long enough, whose length equals the sum of the required $n$ boards, and decided to cut it into the $n$ boards he needs (Ruirui produces no sawdust when cutting, so ignore any loss of length). Ruirui uses a special method: cutting a board of length $x$ into two pieces costs $x$ units of energy. He has endless energy, but in the spirit of saving energy, he wants to minimize the total energy used. Clearly, there must be $(n-1)$ cuts in total. The question is: how should he cut each time? Please compute the minimum possible total energy.}}

{{The first line contains an integer $n$, the number of boards needed. Lines $2$ to $n+1$ each contain one integer. The integer on line $(i+1)$ is $l_i$, the length of the $i$-th board.}}

{{Output a single integer, the minimum total energy required.}}

{{Explanation for Sample 1 Cut the board of length $21$ first into lengths $8$ and $13$, costing $21$ units of energy. Then cut the board of length $13$ into $5$ and $8$, costing $13$ units of energy. The total cost is $34$ units, which is minimal. ---- Constraints - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 2 \times 10^4$, $1 \le l_i \le 5 \times 10^4$.}} Translated by ChatGPT 5