某年级一共有 m=n×k 个学生，编号 1∼m。
其中，第 i个学生的学习能力为 ai。
学校计划将这些学生平均分配到 n个班级，每个班级恰好包含 k 个人。
为了保证全班学生都能跟得上讲课，每个班的讲课速度都等于班级内学习能力最低的学生的学习能力。
学校希望班级之间的学习进度不能相差太多，具体来说，任意两个班级之间的讲课速度的差异都不得超过 l。
在此前提下，学校希望通过合理分班，使得所有班级的讲课速度之和尽可能大。
请你计算并输出所有班级的讲课速度之和的最大可能值。
输入格式
第一行包含三个整数 n,k,l。
第二行包含 m=n×k 个整数 a1,a2,…,am。
输出格式
输出一个整数，表示所有班级的讲课速度之和的最大可能值。
如果不存在满足要求的分班方案，则输出 0。
数据范围
前 44 个测试点满足 1≤m≤10。
所有测试点满足 1≤n,k,m≤ 
，0≤l≤ 
，1≤ai≤ 
。
输入样例1：
4 2 1 2 2 1 2 3 2 2 3
输出样例1：
7
输入样例2：
2 1 0 10 10
输出样例2：
20
输入样例3：
1 2 1 5 2
输出样例3：
2
输入样例4：
3 2 1 1 2 3 4 5 6
输出样例4：
0
贪心：
#include <bits/stdc++.h> using namespace std; long long int a[100005]; long long int n, k, m; long long int l; int main() { // 所有班级的讲课速度之和尽可能大 // 任意两个班级之间的讲课速度的差异都不得超过l：|班级最大讲课速度-最小讲课速度|<=l cin >> n >> k >> l; m = n * k; for (long long int i = 0; i < m; i++) { cin >> a[i]; } sort(a, a + m); // 此时最小讲课速度=a[0] // 为了让所有班级的讲课速度之和尽可能大 // 所以现在从右往左找到第一个与a[0]差值<=l的元素b，将其设为某班的最小值（即此班中k个人，1个人为b,k-1个人>=b） long long int id = m; for (long long int i = m - 1; i >= 0; i--) { if (a[i] - a[0] <= l) { id = i; // 学习能力为b的下标 break; } } long long int ans = 0; long long int need = m - 1 - id; // 除去差值<=l的部分（即need差值>l的部分） for (; id >= 0; id--) // id：一个班级中最小学习能力的最大值的下标 { // need：确保剩余>k个人才能组班 need += 1; // 加上学习能力为b的这个人 if (need >= k) // 可以构成一个班 { need -= k; // 减去一个班的人 ans += a[id]; } } if (need) // 如果还剩下人，这些人不能被组成一个班 { ans = 0; } cout << ans; }
