思维（Python）_牛客博客

参考：https://blog.nowcoder.net/n/9a329387829c45cab18f6e0e409afec0

思路：思维题。base case比较容易想到：1.操作必须同时+1和-1，所以说整个数组和不变；2.要求最大化众数的个数，由于可以进行任意次操作，所以说令 $s = sum(a)$ ，那么当 $s\ \%\ n == 0$ 时，我们可以把数组a中的所有数都变成平均数，他也是众数。那么plus(+1)和sub(-1)操作操作相同，只需要算一个就行。

除去base case以外就不太容易想了，由于 $s\ \%\ n\ != 0$ ，所以说会产生余数，导致数组a中的元素无法都变成平均数，那此时的最大众数有多少个？答案是n - 1个，我们可以选出一个数字来通过和他操作，以存放多余的值。那么这个数字应该怎么选？贪心的想，为了操作最小化，那就应该用最小值或者最大值来存放这些多余的值

接下来就需要分类讨论下了：1.去掉最大值，把剩下的n - 1个数字都变成一样的，也就是剩下数的平均数。但这里的平均数我们需要区分一下是上限还是下限，为什么？因为我们额外拿出了最大值，他其实充当了一个中介，多了数可以给他，少了数可以从他那里拿，所以说上限和下限都能算。具体计算过程就是cal函数写的，排除最大值索引，然后算其他n - 1个数变成上限/下限的plus(+1)和sub(-1)操作数，最终返回其中的最大值，就是我们实际的操作数。那这两个操作数的差值是什么，其实就是额外和最大值(中介)操作的次数

然后就是去掉最小值的情况，他和去掉最大值的情况同理，这里不再过多描述。最后，不断取fmin然后输出结果即可

代码：

import sys
from collections import Counter

input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n = II()
    a = LII()

    s = sum(a)
    if s % n == 0:
        op = 0
        num = s // n
        for x in a:
            op += x - num if x > num else 0
        print(op)
        return

    cur_mx = max(v for v in Counter(a).values())
    if cur_mx == n - 1:
        print(0)
        return

    def cal(p, idx):
        plus = sub = 0
        for i, x in enumerate(a):
            if i == idx:
                continue
            if x < p:
                plus += p - x
            elif x > p:
                sub += x - p
        return fmax(plus, sub)

    m = M = 0
    for i, x in enumerate(a):
        if x > a[M]:
            M = i
        if x < a[m]:
            m = i

    ans = inf
    # 情况1：排除最大值，让其他n-1个数相等
    sum_without_M = s - a[M]
    base = sum_without_M // (n - 1)

    ans = fmin(ans, cal(base, M)) # 下限
    ans = fmin(ans, cal(base + 1, M)) # 上限

    # 情况2：排除最小值，让其他n-1个数相等
    sum_without_m = s - a[m]
    base = sum_without_m // (n - 1)

    ans = fmin(ans, cal(base, m)) # 下限
    ans = fmin(ans, cal(base + 1, m)) # 上限

    print(ans)

t = 1
# t = II()
for _ in range(t):
    solve()