题解 AT2060【[AGC005B] Minimum Sum】

· · 题解

用并查集来贪心。

我们可以把数列抽象成一条 n+1 点 n 边的链，i 与 i+1 之间的边权为 a_i。同时初始化一个有 n+1 个点的并查集，需要记录每个集合的大小。

考虑一条边做出贡献的条件是什么，就是这条边是路径上边权最小的。因此我们将所有边按边权从大到小排序，然后按顺序枚举每一条边，根据它连接的两个连通块的大小和它的边权计算贡献，之后把这条边加到图中（也就是合并它连接的两个连通块）。

由于我们按边权降序枚举，显然在加入一条边时，过这条边的每条路径的最小边权都由这条边贡献。

时间复杂度为 \mathcal{O}(n\log n)。

提交记录