Liebig's Barrels
题意翻译
### 题目描述
你有一共m=n*k个木板。第i个木板的长度为ai。你必须用其中的每k条木板组成n个木桶。每条木板只能且必须属于一个木桶。我们把第j个木桶的最短的木板长度作为这个木桶的容积vj
你想要让这组合起来的n个木桶总容积最大。但是你需要让他们的容积尽量差不多，使得无论那两个木桶的容积差不超过l，即|vx-vy|<=l(1<=vx,vy<=n)。
输出这n个尽量相等的木桶的最大容积。如果无法组成满足要求的n个木桶，输出“0”
### 输入格式
第一行包括三个分开的整数n,k,l(1<=n,k<=10^5, 1<=n·k<=10^5, 0<=l<=10^9)
第二行包括m=n*k个整数，表示木板长度a1,a2,...,am ( 1<=ai<=10^9)
### 输出格式
输出一个整数，即n个满足要求的木桶的容积最大值
感谢@hicc0305 提供的翻译
题目描述
You have $ m=n·k $ wooden staves. The $ i $ -th stave has length $ a_{i} $ . You have to assemble $ n $ barrels consisting of $ k $ staves each, you can use any $ k $ staves to construct a barrel. Each stave must belong to exactly one barrel.
Let volume $ v_{j} $ of barrel $ j $ be equal to the length of the minimal stave in it.
You want to assemble exactly $ n $ barrels with the maximal total sum of volumes. But you have to make them equal enough, so a difference between volumes of any pair of the resulting barrels must not exceed $ l $ , i.e. $ |v_{x}-v_{y}|<=l $ for any $ 1<=x<=n $ and $ 1<=y<=n $ .
Print maximal total sum of volumes of equal enough barrels or $ 0 $ if it's impossible to satisfy the condition above.
输入输出格式
输入格式
The first line contains three space-separated integers $ n $ , $ k $ and $ l $ ( $ 1<=n,k<=10^{5} $ , $ 1<=n·k<=10^{5} $ , $ 0<=l<=10^{9} $ ).
The second line contains $ m=n·k $ space-separated integers $ a_{1},a_{2},...,a_{m} $ ( $ 1<=a_{i}<=10^{9} $ ) — lengths of staves.
输出格式
Print single integer — maximal total sum of the volumes of barrels or $ 0 $ if it's impossible to construct exactly $ n $ barrels satisfying the condition $ |v_{x}-v_{y}|<=l $ for any $ 1<=x<=n $ and $ 1<=y<=n $ .
输入输出样例
输入样例 #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
说明
In the first example you can form the following barrels: $ [1,2] $ , $ [2,2] $ , $ [2,3] $ , $ [2,3] $ .
In the second example you can form the following barrels: $ [10] $ , $ [10] $ .
In the third example you can form the following barrels: $ [2,5] $ .
In the fourth example difference between volumes of barrels in any partition is at least $ 2 $ so it is impossible to make barrels equal enough.