最小增量数-使所有数组元素相等的其他操作

Question

我正在为极客网站阅读极客的这问题。

问题是如何在数组中找到最小移动次数，以便所有元素都相等。

给出了一个由n个元素组成的数组。在每个操作中，您可以选择任意一个元素，并将n-1元素的其余部分增加1。查找此操作所需的最小操作数。

Examples:

Input : arr[] = {1, 2, 3}
Output : Minimum Operation = 3
Explanation : 
operation | increased elements | after increment
    1     |    1, 2            | 2, 3, 3
    2     |    1, 2            | 3, 4, 3
    3     |    1, 3            | 4, 4, 4

Input : arr[] = {4, 3, 4}
Output : Minimum Operation = 2
Explanation : 
operation | increased elements | after increment
     1    |    1, 2           | 5, 4, 4
     2    |    2, 3           | 5, 5, 5

链接解释说，我们必须使用公式minOperation = sum - (n * small)来得到答案，其中和是数组中所有元素的总和，n是数组中的元素数，小元素是数组中最小的元素。

你能帮我理解这个公式表示minOperation = sum - (n * small)的意思吗？以及它如何解决这个问题？

Answer 1

编辑1:为了更好地联系这个解决方案，最好提到用户杜克林在他的评论中说了些什么。也就是说，增加除最大元素以外的所有其他元素类似于只减少最大元素。

现在，想象一下你正试图平整许多砖柱。每个砖柱可以是不同的层次：

为了平平所有的砖柱，你总是挑出最高的一栏，每次移除一块砖。

重复此过程，直到所有列都平平为止。

​

那些涂上黄色颜色的砖块是你为了达到目标而需要拆除的砖块。(它们也是指你需要执行的达到目标的操作数量)。

为了计算红砖的数量，你使用了一个类似矩形面积的简单公式，那就是长度x宽度。

min x number of columns = all the red bricks (to be remained untouched)

sum of all bricks - number of red bricks = all yellow bricks 

因此，您有一个公式：

minOperation = sum - (n * small) 

​

​

黄色数=使所有数组元素相等所需的最少操作数。

Answer 2

使用一个简单的公式：

数组元素之和-(数组的大小*数组中的最小元素)

示例数组= {1，2，3，4，5} n=5 //数组大小

和= 15，最小=1

ans = sum - (min * n) = 10

均匀阵列 数组 砖块问题

Answer 3

我已经用二进制搜索解决了这个问题！

def main():
#codechef question SALARY 
t = input()
t = int(t)
while t > 0:
    n = input()
    n = int(n)
    val = list(map(int, input().split(" ")))
    initial_sum = sum(val)
    min_value = min(val)
    left = 0
    right = 10000000000
    while left <= right:
        mid = (left + right) // 2
        may_be = initial_sum + (mid * (n-1))
        mean = may_be / n
        diff = mean - min_value
        if diff == mid:
            break
        elif diff < mid:
            right = mid - 1
        else:
            left = mid + 1
    print(mid)
    t -= 1

如果名称为 == 'main'：main()