#YHCSPJMN100001. 和谐组合
和谐组合
和谐组合
题目背景
在育华学校组织的数学实践活动中,有一个关于学生分组的趣味问题。活动中,需将若干学生每3人分为一组,每个学生手上有一个数字,小组的“不和谐程度”定义为组内数字最大值与最小值的差值。现在要通过合理分组,让所有小组不和谐程度之和最小,以此锻炼同学们的算法设计与优化能力,理解贪心策略在分组问题中的应用。
题目描述
有 个学生( 是3的倍数 ),每个学生对应一个数字 。需将学生每3人分一组,小组的不和谐程度为组内 最大值与最小值的差值。目标是通过分组,使所有小组不和谐程度之和最小,输出这个最小的总和。
输入格式
- 第一行:正整数 ,表示学生数量( 是3的倍数 )。
- 第二行: 个正整数 ,表示每个学生的数字。
输出格式
输出一行一个整数,为所有小组不和谐程度之和的最小值。
样例
样例输入 1
6
3 7 5 5 5 9
样例输出 1
6
样例说明
最优分组为:[3,7,9](不和谐程度 )和 [5,5,5](不和谐程度 ),总和 。若分组为 [3,5,7] 和 [5,9,5] ,总和为 ,不是最优。
数据规模与测试点
测试点编号 | 范围 | 特殊性质 |
---|---|---|
1-4 | ||
5-8 | , | 所有 相等 |
9-10 | 所有 不同 | |
11-12 | ||
13-16 | ||
17-20 |
对所有的数据,有
相关
在下列比赛中: