#YHCSPJMN100001. 和谐组合

和谐组合

和谐组合

题目背景

在育华学校组织的数学实践活动中,有一个关于学生分组的趣味问题。活动中,需将若干学生每3人分为一组,每个学生手上有一个数字,小组的“不和谐程度”定义为组内数字最大值与最小值的差值。现在要通过合理分组,让所有小组不和谐程度之和最小,以此锻炼同学们的算法设计与优化能力,理解贪心策略在分组问题中的应用。

题目描述

n n 个学生(n n 是3的倍数 ),每个学生对应一个数字 ai a_i 。需将学生每3人分一组,小组的不和谐程度为组内 ai a_i 最大值与最小值的差值。目标是通过分组,使所有小组不和谐程度之和最小,输出这个最小的总和。

输入格式

  1. 第一行:正整数 n n ,表示学生数量(n n 是3的倍数 )。
  2. 第二行:n n 个正整数 a1,a2,,an a_1, a_2, \dots, a_n ,表示每个学生的数字。

输出格式

输出一行一个整数,为所有小组不和谐程度之和的最小值。

样例

样例输入 1

6  
3 7 5 5 5 9  

样例输出 1

6  

样例说明

最优分组为:[3,7,9](不和谐程度 93=6 9 - 3 = 6 )和 [5,5,5](不和谐程度 55=0 5 - 5 = 0 ),总和 6+0=6 6 + 0 = 6 。若分组为 [3,5,7] 和 [5,9,5] ,总和为 4+4=8 4 + 4 = 8 ,不是最优。

数据规模与测试点

测试点编号 n n 范围 特殊性质
1-4 n=3 n = 3
5-8 n105 n \leq 10^5 所有 ai a_i 相等
9-10 所有 ai a_i 不同
11-12 n=6 n = 6
13-16 n103 n \leq 10^3
17-20 n105 n \leq 10^5

对所有的数据,有 1ai109 1 \leq a_i \leq 10^9