题目描述

$\text{Samuel}$ 购买了一批大小不同的白色画布，希望通过一台自动绘画机将它们全部涂成互不相同的颜色。 绘画过程如下：

1. 将所有画布按某种顺序排列在传送带上。
2. 选择一种颜色 $C$ 和一个数字 $F$（$F$ 小于颜色 $C$ 的画布数量）。
3. 从左到右，将所有颜色为 $C$ 的画布重新涂色：前 $F$ 个涂成新颜色 $X$，其余的涂成新颜色 $Y$。 $X$ 和 $Y$ 互不相同，且与之前使用过的所有颜色都不同。 此步骤消耗的墨水量等于被涂色的画布大小之和。
4. 重复步骤 2 和 3，直到所有画布颜色都不同。

给定每个画布的大小，求机器完成绘画所需的最小墨水量。

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例由两行组成：
  • 第一行包含一个整数 $N$，表示画布的数量。
  • 第二行包含 $N$ 个用空格分隔的整数，表示每个画布的大小。

约束条件：

• $1\le T\le 100$
• $1\le N_i\le 100000$
• $1\le s\le 100000$
• ${\sum }_{i=1}^T{N}_i\le 100000$

输出格式

对于每个测试用例，输出一行，表示所需的最小墨水量。

样例

输入：

2
3
7 4 7
4
5 3 7 5

输出：

29
40

题目分析

问题转化

首先理解操作的本质：每次选择一种颜色的所有画布，将其分成两个新颜色的组（前 $F$ 个和后 $N-F$ 个）。 每次操作的墨水消耗等于被涂色的画布大小之和，也就是该组所有画布的大小之和。

我们的目标是将所有画布最终分成 $N$ 个独立的组（每个组只有一张画布），使得整个过程中所有操作消耗的墨水总量最小。

这实际上是一个 分裂问题 ：初始时，所有相同大小的画布可以被视为同一个颜色组（因为题目允许我们任意排列画布顺序，所以我们可以将相同大小的画布视为初始颜色相同）。 每次分裂一个组时，消耗的墨水等于该组所有画布的大小之和。 分裂后得到两个新组，它们的大小之和等于原组的大小之和。

逆向思考：合并问题

如果正向考虑分裂过程，很难直接找到最优策略。 但我们可以 逆向思考 ：

• 最终状态： $N$ 个组，每个组包含一个画布。
• 初始状态：若干个组（相同大小的画布属于同一组）。
• 每次操作（分裂）的逆操作是 合并 ：将两个组合并成一个组，合并的墨水消耗等于合并后组的总大小（因为正向分裂时，分裂该组消耗的墨水等于该组总大小）。

因此，问题转化为：从最终状态（ $N$ 个单画布组）开始，每次选择两个组合并，合并成本为合并后组的总大小，最终合并成初始的若干个组，使得总合并成本最小。 注意，初始组的大小就是该组所有画布的大小之和。

哈夫曼编码模型

这个问题与 哈夫曼编码（$\text{Huffman Coding}$） 的构造过程完全相同：

• 每个画布的大小视为一个“频率”（或权重）。
• 每次合并两个最小的权重，合并成本为它们的和。
• 重复此过程，直到所有权重合并成一个。
• 总合并成本就是最小墨水量。

为什么哈夫曼算法能得到最优解？
因为哈夫曼算法每次合并当前最小的两个元素，这保证了全局合并成本最小。 在本问题中，合并成本（即墨水消耗）的累加正好对应了正向分裂过程中每一步的消耗。

算法步骤

对于每个测试用例：

1. 读取所有画布的大小，存入最小堆（优先队列）中。
2. 当堆中元素多于 $1$ 个时：
   • 取出最小的两个数 $a$ 和 $b$。
   • 计算 $sum=a+b$，将 $sum$ 累加到答案中。
   • 将 $sum$ 放回堆中。
3. 当堆中只剩一个元素时，累加的总和即为最小墨水量。

时间复杂度： $O(N\log N)$，其中 $N$ 为画布数量。
空间复杂度： $O(N)$。

代码实现

// Canvas Painting
// UVa ID: 13017
// Verdict: Accepted
// Submission Date: 2025-12-05
// UVa Run Time: 0.180s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        // 使用最小堆存储所有画布的大小
        priority_queue<long long, vector<long long>, greater<long long>> minHeap;
        for (int i = 0; i < n; ++i) {
            long long size;
            cin >> size;
            minHeap.push(size);
        }

        long long totalInk = 0;
        // 哈夫曼合并过程
        while (minHeap.size() > 1) {
            long long a = minHeap.top(); minHeap.pop();
            long long b = minHeap.top(); minHeap.pop();
            long long sum = a + b;
            totalInk += sum;
            minHeap.push(sum);
        }

        cout << totalInk << "\n";
    }

    return 0;
}

总结

本题的关键在于将看似复杂的“分裂”过程转化为经典的 哈夫曼合并问题 。 通过逆向思考，我们发现最小墨水量等于将所有画布大小作为叶子节点构建哈夫曼树时，所有非叶子节点权值之和。 使用最小堆（优先队列）可以高效地实现哈夫曼算法，从而在 $O(N\log N)$ 时间内解决问题。

这种逆向思维和模型转化在竞赛编程中非常常见，遇到类似“分裂/合并”成本最小化的问题时，哈夫曼算法往往是一个有力的工具。