CF671B Robin Hood

我们都知道罗宾汉的传奇故事。罗宾汉凭借他高超的箭术和智慧，从富人那里偷取金钱，并将其归还给穷人。 在 Kekoland 有 $n$ 个市民，每个人拥有 $c_{i}$ 个硬币。每天，罗宾汉会从全市最富有的人手中拿走恰好 $1$ 个硬币，并将其给到最贫穷的人（在拿走富人一个硬币之后当前最贫穷的那个人）。如果有多个人同为最富或者最穷，罗宾汉会随机选择其中一人。可惜的是，罗宾汉已经年老，打算在 $k$ 天后退休。在最后这几天里，他决定帮助贫苦的人们。 在罗宾汉分配硬币后，最富的人可能变成最穷的人，甚至可能刚刚最富的人又立即成为最穷的。比如，如果所有人拥有的硬币数量相同，则下一天大家的硬币数仍然相同。 你的任务是求出 $k$ 天后最富和最穷的人财富的差值。请注意，在有多人最大或最小时随机选择，不会影响答案。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 500000, \, 0 \leq k \leq 10^{9}$）—— Kekoland 的市民人数，以及距离罗宾汉退休还有多少天。 第二行包含 $n$ 个整数，第 $i$ 个为 $c_{i}$（$1 \leq c_{i} \leq 10^{9}$）—— 每个人初始拥有的硬币数。

输出一行，表示 $k$ 天后最富有者和最穷者之间财富的差值。

我们来看第一个样例中财富随天数的变化。 1. $[1,1,4,2]$ 2. $[2,1,3,2]$ 或 $[1,2,3,2]$ 因此答案为 $3-1=2$。 在第二个样例中，每个人的财富都保持不变。 由 ChatGPT 5 翻译