{"problem":{"name":"D. Boxes And Balls","description":{"content":"Ivan has _n_ different boxes. The first of them contains some balls of _n_ different colors. Ivan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for ever","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF884D"},"statements":[{"statement_type":"Markdown","content":"Ivan has _n_ different boxes. The first of them contains some balls of _n_ different colors.\n\nIvan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for every _i_ (1 ≤ _i_ ≤ _n_) _i_\\-th box will contain all balls with color _i_.\n\nIn order to do this, Ivan will make some turns. Each turn he does the following:\n\n1.  Ivan chooses any non-empty box and takes all balls from this box;\n2.  Then Ivan chooses any _k_ empty boxes (the box from the first step becomes empty, and Ivan is allowed to choose it), separates the balls he took on the previous step into _k_ non-empty groups and puts each group into one of the boxes. He should put each group into a separate box. He can choose either _k_ = 2 or _k_ = 3.\n\nThe _penalty_ of the turn is the number of balls Ivan takes from the box during the first step of the turn. And _penalty_ of the game is the total _penalty_ of turns made by Ivan until he distributes all balls to corresponding boxes.\n\nHelp Ivan to determine the minimum possible _penalty_ of the game!\n\n## Input\n\nThe first line contains one integer number _n_ (1 ≤ _n_ ≤ 200000) — the number of boxes and colors.\n\nThe second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109), where _a__i_ is the number of balls with color _i_.\n\n## Output\n\nPrint one number — the minimum possible _penalty_ of the game.\n\n[samples]\n\n## Note\n\nIn the first example you take all the balls from the first box, choose _k_ = 3 and sort all colors to corresponding boxes. Penalty is 6.\n\nIn the second example you make two turns:\n\n1.  Take all the balls from the first box, choose _k_ = 3, put balls of color 3 to the third box, of color 4 — to the fourth box and the rest put back into the first box. Penalty is 14;\n2.  Take all the balls from the first box, choose _k_ = 2, put balls of color 1 to the first box, of color 2 — to the second box. Penalty is 5.\n\nTotal penalty is 19.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Ivan 有 #cf_span[n] 个不同的盒子。第一个盒子中装有 #cf_span[n] 种不同颜色的球。\n\nIvan 想玩一个奇怪的游戏。他希望将球分配到各个盒子中，使得对于每个 #cf_span[i]（#cf_span[1 ≤ i ≤ n]），第 #cf_span[i] 个盒子中只包含颜色为 #cf_span[i] 的球。\n\n为了实现这一目标，Ivan 将进行若干轮操作。每一轮他执行以下步骤：\n\n每轮的 _惩罚_ 是他在该轮第一步中从盒子中取出的球的数量。游戏的 _惩罚_ 是 Ivan 将所有球分配到对应盒子之前所进行的所有轮次的惩罚之和。\n\n请帮助 Ivan 确定游戏的最小可能 _惩罚_！\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200000]）——盒子和颜色的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示颜色为 #cf_span[i] 的球的数量。\n\n请输出一个数——游戏的最小可能 _惩罚_。\n\n在第一个例子中，你从第一个盒子中取出所有球，选择 #cf_span[k = 3]，并将所有颜色的球分配到对应的盒子中。惩罚为 #cf_span[6]。\n\n在第二个例子中，你进行了两轮操作：\n\n总惩罚为 #cf_span[19]。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200000]）——盒子和颜色的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 109]），其中 #cf_span[ai] 表示颜色为 #cf_span[i] 的球的数量。\n\n## Output\n\n请输出一个数——游戏的最小可能 _惩罚_。\n\n[samples]\n\n## Note\n\n在第一个例子中，你从第一个盒子中取出所有球，选择 #cf_span[k = 3]，并将所有颜色的球分配到对应的盒子中。惩罚为 #cf_span[6]。在第二个例子中，你进行了两轮操作：\n\n取出第一个盒子中的所有球，选择 #cf_span[k = 3]，将颜色为 #cf_span[3] 的球放入第三个盒子，颜色为 #cf_span[4] 的球放入第四个盒子，其余球放回第一个盒子。惩罚为 #cf_span[14]；\n\n取出第一个盒子中的所有球，选择 #cf_span[k = 2]，将颜色为 #cf_span[1] 的球放入第一个盒子，颜色为 #cf_span[2] 的球放入第二个盒子。惩罚为 #cf_span[5]。总惩罚为 #cf_span[19]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of boxes and colors. Let $ a_1, a_2, \\dots, a_n $ be the number of balls of each color, initially all in box 1.\n\nIn each move, Ivan may:\n- Select a non-empty box containing balls of multiple colors.\n- Take **all** balls from that box (penalty = number of balls in the box).\n- Distribute them into their respective target boxes (i.e., ball of color $ i $ goes to box $ i $).\n\nThe goal is to minimize the total penalty.\n\nThis is equivalent to the problem of **minimum cost to merge piles** where:\n- Initially, all balls are in one pile (box 1).\n- We wish to partition the multiset of balls into $ n $ singleton piles (each color in its own box).\n- The cost of splitting a pile is equal to its size.\n- We can split a pile into any number of sub-piles (not just binary splits).\n\nThis is a classic problem solvable by **Huffman coding** or **greedy merging in reverse**.\n\n### Key Insight:\nThe process is equivalent to building a tree where:\n- Each leaf corresponds to a color with weight $ a_i $.\n- Each internal node corresponds to a merge (or split) operation.\n- The cost is the sum of all internal node weights.\n\nBut note: **We start with one pile and split it**. The total penalty is the sum of the sizes of all piles ever taken during splits.\n\nThis is equivalent to the **minimum total cost to split** the initial pile into singletons, where splitting a pile of size $ s $ into $ k $ sub-piles costs $ s $, and the sub-piles are then split recursively.\n\nThis is dual to the **Huffman coding problem** for merging: the minimum cost to split is the same as the minimum cost to merge if we reverse the process.\n\nThus, the minimal total penalty equals the **total weight of the Huffman tree** built from the multiset $ \\{a_1, a_2, \\dots, a_n\\} $, i.e., the sum of all internal nodes when merging the smallest two piles repeatedly until one remains.\n\nBut wait — in the **merging** version, we start with $ n $ piles and merge two at a time until one pile remains. The cost is the sum of the merged piles at each step.\n\nIn our case, we start with one pile and split until we have $ n $ piles. The total penalty is the sum of the sizes of the piles we split.\n\nIt turns out: **The minimal total penalty is equal to the total cost of the Huffman tree built from the $ a_i $'s**.\n\nWhy? Because the splitting tree is the reverse of the merging tree. The sum of the internal nodes (which is the penalty) is identical.\n\n### Formal Statement:\n\nLet $ a_1, a_2, \\dots, a_n \\in \\mathbb{N}^+ $ be given.\n\nDefine $ T $ as the minimum total cost to merge $ n $ piles of sizes $ a_i $ into one pile, where the cost of merging two piles of sizes $ x $ and $ y $ is $ x + y $, and total cost is the sum of all merge costs.\n\nThen the minimal penalty for the splitting game is exactly $ T $.\n\nThis is computed by:\n\n- Use a min-heap (priority queue).\n- Repeatedly extract two smallest elements $ x, y $, merge them with cost $ x+y $, and insert $ x+y $ back.\n- Accumulate the cost.\n\nThe final accumulated sum is the minimal penalty.\n\n### Mathematical Formulation:\n\nLet $ S = \\sum_{i=1}^n a_i $.\n\nThe minimal penalty is:\n\n$$\n\\boxed{\\sum_{\\text{all internal nodes } v} \\text{weight}(v)}\n$$\n\nwhere the tree is the Huffman tree for the multiset $ \\{a_1, \\dots, a_n\\} $, built by repeatedly combining the two smallest weights.\n\nThis is computed algorithmically as:\n\nInitialize a min-heap $ H $ with elements $ a_1, a_2, \\dots, a_n $.\n\nInitialize $ \\text{penalty} = 0 $.\n\nWhile $ |H| > 1 $:\n- Extract minimum $ x = \\text{heappop}(H) $\n- Extract minimum $ y = \\text{heappop}(H) $\n- $ \\text{penalty} \\gets \\text{penalty} + x + y $\n- Insert $ x + y $ into $ H $\n\nReturn $ \\text{penalty} $\n\n---\n\n**Final Answer (Formal Output):**\n\nGiven $ n \\in \\mathbb{N} $, and $ a_1, a_2, \\dots, a_n \\in \\mathbb{N}^+ $, the minimum penalty is:\n\n$$\n\\boxed{\\sum_{k=1}^{n-1} (x_k + y_k)}\n$$\n\nwhere $ (x_1, y_1), (x_2, y_2), \\dots, (x_{n-1}, y_{n-1}) $ are the pairs of smallest elements merged in sequence in the Huffman algorithm.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF884D","tags":["data structures","greedy"],"sample_group":[["3\n1 2 3","6"],["4\n2 3 4 5","19"]],"created_at":"2026-03-03 11:00:39"}}