微信开发中 ACCESS TOKEN 过期失效的解决方案详解
527
2022-10-21
C. Liebig's Barrels (贪心)
C. Liebig's Barrels
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
Input
The 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.
Output
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 |vx - vy| ≤ l for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.
Examples
input Copy
4 2 12 2 1 2 3 2 2 3
output Copy
7
input Copy
2 1 010 10
output Copy
20
input Copy
1 2 15 2
output Copy
2
input Copy
3 2 11 2 3 4 5 6
output Copy
0
思路:
一道很贪心的贪心题。
比赛时,第一次思路想简单了,我也很感慨我当时能回归正途。
先找出符合 l 的最长的木板,然后木桶装水最多为l,就用比l长的(k-1)块木板,从 l 到 最小 开始组合。如果还有剩余的,然后再从大到小选出k个一组,组合。
代码:
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~