Educational Codeforces Round 44 (Rated for Div. 2)
Educational Codeforces Round 44 (Rated for Div 2) 。
You have m=n·k wooden staves. The i-th stave has length ai. 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 vj 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. |vx-vy|≤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.
InputThe first line contains three space-separated integers n, k and l (1≤n,k≤105, 1≤n·k≤105, 0≤l≤109).
The second line contains m=n·k space-separated integers a1,a2,...,am (1≤ai≤109) — lengths of staves.
OutputPrint single integer — maximal total sum of the volumes of barrels or 0 if it's impossible to construct exactly n barrels satisfying the condition |vx-vy|≤l for any 1≤x≤n and 1≤y≤n.
ExamplesInputCopy4 2 1 2 2 1 2 3 2 2 3OutputCopy
7InputCopy
2 1 0 10 10OutputCopy
20InputCopy
1 2 1 5 2OutputCopy
2InputCopy
3 2 1 1 2 3 4 5 6OutputCopy
0
Note
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.
这道题忍住了看题解。自己独立思考了QAQ。 但是div2的C题还是属于那种自己可以做但需要花很长时间的那种,希望慢慢进步(D题先凑合着题解自己写QAQ)补完了这道题去洗澡澡 题意很简单,给n,k,l, l是体积限定的条件见上,k是每个小序列的长度,n是小序列的个数。再给你N*K个数这道题是一道贪心的题目,我的想法是对于这一系列数字来说:对于分成的k个序列,每个序列中最小的就是代表这个体积,在符合情况| Vi-Vj |<=l的情况下取尽可能大的体积。 首先对数组排序,首先排序后的arr[1]肯定是一个序列的体积(放哪里都是最小的),那么我要满足l的限定条件的话,体积的取值一定在arr[1]~arr[1]+l中,找到arr[1]+l这个值所对应的数组下标。 对于一般情况,n<>
再考虑涵盖不掉全部的情况,比如刚才的例子,对于刚刚的6来说,只剩下6和7了,自然涵盖完,但是如果n是3呢,就只能一个取6 一个取7,单独判断一下就好(k不行变成k-1一直减到0为止(保证k过后剩下的元素个数大于等于还没取得序列个数))说了一大堆,上代码(懒得加注释了改了好多遍才过之前一直WA7是用样例推得时候最小为1,就一直l+1到好久....) 菜啊qwq
#include#include #include #include #include #include #include #include #include #include #include