最大生成树(Maximum Spanning Tree)

题目描述

树是一张 $n$ 个节点和 $n-1$ 条边的无向连通图，一个无向图的最大生成树是在所有生成树中边权值和最大的生成树。

给定一个 $n$ 个点的完全图，每个点有点权 $a_i$ ，两个点之间的边权是 $|a_i-a_j |$ ，请你求出这个图的最大生成树。

输入格式

一行一个整数 $n$

一行 $n$ 个整数 $a_i$ ，表示每个点的点权。

输出格式

一个整数表示答案。

样例输入 #1

4
1 6 7 3

样例输出 #1

15

数据范围

对于 $30\%$ 的数据，$n\leq 10$

对于 $50\%$ 的数据，$n\leq 1000$

对于 $70\%$ 的数据，$n\leq 5000$

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq a_i\leq 10^{9}$。

知识点与难度

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1300。

测试点分布

出处：原题链接