题目解析
1. 首先考虑 L=A1+A2+…+ANL=A_1+A_2+\ldots +A_NL=A1 +A2 +…+AN 的情况：
反转问题为：“使用 x+yx + yx+y 的成本将原本长度为 xxx 和 yyy 的面包拼接在一起，求将面包 A1,…,ANA_1, \ldots, A_NA1 ,…,AN 合并为一个面包的最小费用。”
这个问题和原问题等价。
在这里，原问题的最小费用等于在多重集 S={A1,A2,…,AN}S=\{ A_1,A_2,\ldots,A_N \}S={A1 ,A2 ,…,AN } 上重复以下操作 (N−1)(N-1)(N−1) 次的成本之和：
* 令 s1s_1s1 和 s2s_2s2 为 SSS 中最小的两个元素。以 s1+s2s_1+s_2s1 +s2 的成本将长度为 s1s_1s1 和 s2s_2s2 的两条面包拼接在一起。
* 从 SSS 中删除 s1s_1s1 和 s2s_2s2 ，并将 s1+s2s_1+s_2s1 +s2 插入到 SSS 中。
由于每次操作后 SSS 的元素数量减少 111，显然完成以上操作后，SSS 只会剩下一个元素。
2. 考虑 L>A1+A2+…+ANL \gt A_1+A_2+\ldots +A_NL>A1 +A2 +…+AN 的情况：
对于 L>A1+A2+⋯+ANL > A_1+A_2+\cdots+A_NL>A1 +A2 +⋯+AN ，我们可以令 L=A1+A2+⋯+AN+XL = A_1 + A_2 + \cdots + A_N + XL=A1 +A2 +⋯+AN +X。
将剩余的部分当作一条面包，反转问题为：“使用 x+yx + yx+y 的成本将原本长度为 xxx 和 yyy 的面包拼接在一起，求将面包 A1,…,AN,XA_1, \ldots, A_N, XA1 ,…,AN ,X 合并为一条面包的最小费用。”
这个问题同样可以使用上述的方法解决。
AC代码
C++ AC代码：
Python AC代码：
复杂度分析
使用「有序集合」或「优先队列」等数据结构充当集合 SSS，在 O(NlogN)\mathrm{O}(N\log{N})O(NlogN) 的时间复杂度完成处理。
