CF1256E Yet Another Division Into Teams

你的大学里面有 $n$ 个学生，第 $i$ 个学生的水平为 $a_i$。作为一名教练，你想把他们分成若干个队伍已准备即将到来的 ICPC 决赛。 每一支队伍至少要有三名学生，并且每一位学生恰好属于一支队伍。定义一支队伍的极差为所有这支队伍的学生中水平最高的与最低的的水平之差。形式化的说，如果一支队伍中有 $k$ 个学生，水平分别为 $a_{i_1},a_{i_2},\cdots,a_{i_n}$，那么这支队伍的极差为 $\max\limits_{j=1}^{k}a_{i_j}-\min\limits_{j=1}^{k}a_{i_j}$。 总共的极差为所有队伍的极差之和。 你需要找到一种最优的分组方案使得总共的极差最小。

第一行一个整数 $n(1\leq n\leq 2\times 10^5)$ ，表示学生的人数。 第二行$n$个整数 $a_1,a_2,\cdots,a_n(1\leq a_i\leq 10^9)$，其中 $a_i$ 表示第 $i$ 个学生的水平。

第一行两个整数 $res,k$，表示最小的总共的极差以及最优方案中队伍的个数。 第二行 $n$ 个整数 $t_1,t_2,\cdots t_n(1\leq t_i\leq k)$，其中 $t_i$ 是第 $i$ 个学生所属的队伍编号。 如果有多种答案，你可以输出任意一个。注意到你不必最小化队伍的数量。每支队伍至少要有三个学生。 Translated By Karry5307

In the first example, there is only one team with skills $ [1, 1, 2, 3, 4] $ so the answer is $ 3 $ . It can be shown that you cannot achieve a better answer. In the second example, there are two teams with skills $ [1, 2, 5] $ and $ [12, 13, 15] $ so the answer is $ 4 + 3 = 7 $ . In the third example, there are three teams with skills $ [1, 2, 5] $ , $ [129, 185, 581, 1041] $ and $ [1580, 1909, 8150] $ so the answer is $ 4 + 912 + 6570 = 7486 $ .