Problem 1040. -- 基于小塔的改造问题

1040: 基于小塔的改造问题

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 14  Solved: 1
[Submit][Status][Web Board]

Description

低调而又正直的咕噜姐少男(简称:DD而又ZZ的咕噜姐少男)放暑假没事闲着在家堆积木。现在他已经用n(1 <= n <= 1,000)个积木砌成了一些小塔。每个小塔都是使用1*1*1的单位立方体竖直堆砌而成。现在dd而又zz的咕噜姐少男同学有一个新的想法,他可以从任何一个或多个塔中去除至多m(<=100,000)个立方体,使得所有小塔当中,最高的小塔和最矮的小塔高度差最小。

Input

第一行一个整数T,表示有T组测试数据,对于每组数据:第一行2个正整数n,m(1 <= n <= 1,000, 0 <= m <= 100,000)。
接下来一行有n个以空格隔开的正整数:h1,h2,……,hn。(1 <= hi <= 100)表示每一个小塔对应的高度。

Output

对于每一组数据:一个正整数表示最后得到的最少的高度差。

Sample Input

2
4 0
1 2 2 5
4 1
1 2 2 5

Sample Output

4
3

HINT

1、可以去除0个或多个单位立方体,但是不能超过m个;
2、一旦某个小塔高度变成0,那么它将不参与高度差计算当中;

Source

[Submit][Status]