P3612.第2题-滴答
题目内容
仓库里一大批货到了。它们被杂乱地摆成了 n 堆，第 i 堆有 ai 个箱子。为了让仓库里的货物尽可能平均，小红型号机器人开始出动了!
小红机器人每接收到一次平均货物的信号，即通讯器的一次“滴答”声，就会自动去把箱子数最多的那一堆，如第 j 堆，拿出一个箱子，然后把这个箱子放到箱子数当前(已经拿走一个箱子后的当前状态)最少的那一堆，如第 k 堆，如果有多个堆箱子数都一样多，任选即可。注意，存在一种情况 j=k (所有堆箱子数相同时)，小红机器人完成这一次操作后相当于没有放置，也是合法的操作。
目前通讯器发出了 m 次滴答声，小红机器人如果完成了所有操作，箱子数最多的堆和箱子数最少的堆数量之差是多少呢?
输入描述
第一行 1 个整数 T ，表示数据组数。
对每组数据，有 2 行。
第一行两个整数 n 和 m ，表示货物堆数，和通讯器的滴答声数量。
第二行 n 个整数 a1,a2,...,an 表示每堆货物的初始箱子数。
对于 100% 的数据：1≤T≤5，1≤n≤100000，1≤m≤2000000000,1≤ai≤2000000000
输出描述
对于每组数据，输出一行一个整数表示答案。
样例1
输入
3
5 1
1 2 3 4 5
5 2
1 2 3 4 5
5 3
1 2 3 4 5
输出
2
2
0
说明
初始箱子为
1 2 3 4 5
第一次滴答声后变成：
2 2 3 4 4（第 5 堆搬了一个箱子到了第 1 堆）
此时最大箱子数和最小箱子数之差为 4−2=2
第二次滴答声后变成
2 3 3 4 3（第 5 堆或者第 4 堆搬了一个箱子到第 1 堆或者第 2 堆，注意顺序不同不影响最终答案）
此时最大箱子数和最小箱子数之差为 4−2=2
第三次滴答声后变成
3 3 3 3 3（箱子数为 4 的堆搬了一个箱子到箱子数为 2 的堆）
此时最大箱子数和最小箱子数之差为 3−3=0
