显然,要让极差最小,只需要将所有数都靠近平均值就行了。
如果所有数都可以变成平均值,那么极差为0,否则极差为1。
设平均值为x(向下取整),当极差为1时,数组为若干个x和若干个x+1
小明拥有 n 堆糖果,其中第 i 堆的初始数量为 ai 颗。每次操作可以选择两堆不同的糖果,从其中一堆取出一颗放入另一堆。小明希望通过若干次操作,使得所有堆的糖果数量尽可能接近,即糖果堆的极差(最多的一堆与最少的一堆的数量之差)达到理论最小值。请求出达到该极差所需的最少操作次数。
糖果堆数 n 满足 2≤n≤105,每堆糖果的初始数量均为不超过 109 的正整数。
第一行包含一个整数 n,表示糖果堆的数量。 第二行包含 n 个整数,依次表示各堆糖果的初始数量 a1,a2,…,an,相邻整数之间以空格分隔。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.