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

1040: 基于小塔的改造问题

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

题目描述

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

输入

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

输出

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

样例输入 Copy

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

样例输出 Copy

4
3

提示

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

来源/分类