和谐分组
测试数据来自 wjszez/1828
【问题描述】
s班共有 n名学生,按照学号从 1到的顺序每名学生的身高分别为 a[1],a[2]...a[n]。
由于是新学期,s 班需要进行分组,分组的要求如下:
1. 进行分组的组数不能超过 k。
2. 每组的人的学号必须相邻。
由于身高差过大的人分在同一个组会激起组内内部矛盾(QAQ),所以我们定义一个分
组方案的不和谐度为每个组的身高极差(最高的身高-最矮的身高)的最大值。
我们希望最小化这个不和谐度,输出这个不和谐度。
【输入格式】
第一行包括两个正整数 n,k。
第二行包括用空格隔开的 n 个正整数,第 i个正整数描述学号为 i的学生的身高。
【输出格式】
一行包括一个整数,表示不和谐度最小的分组方案的不和谐度。
【输入样例】
8 3
5 7 2 3 8 5 9 4
【输出样例】
5
【样例解释】
一种可能的分组是 5 7 2 / 3 8 5 / 9 4
信息
- ID
- 1866
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者