题解 | #小美的数组操作#

思路

众数个数为n或者n-1
当数组平均值k为整数，众数个数为n个，众数为k；
否则众数个数为n-1个，对数组排序，众数可以是前n-1个数的均值向下取整k和k+1，后n-1个数的均值向下取整k和k+1，求出操作次数最小的。

代码

package main

/*
    众数个数为n或者n-1
    当数组平均值k为整数，众数个数为n个，众数为k；
    否则众数个数为n-1个，对数组排序，众数可以是前n-1个数的均值向下取整k和k+1，后n-1个数的均值向下取整k和k+1，求出操作次数最小的。
*/
import (
    "fmt"
    "sort"
    "math"
)



const N = 1e5 + 10
var a = make([]int, N)

func max(a, b int) (int) {
    if(a > b)  {
        return a
    }
    return b
}

func min(a, b int) (int) {
    if(a < b) {
        return a
    }
    return b
}

func getstp(k, l, r int) (int) {
    stp1 := 0
    stp2 := 0

    for i := l; i <= r; i++ {
        if(a[i] < k) {
            stp1 += (k - a[i])
        } else if(a[i] > k) {
            stp2 += a[i] - k
        }
    }
    return max(stp1, stp2)
}

func main() {
    n := 0
    fmt.Scan(&n)
   
    var s, s1, s2 int

    for i := 0; i < n; i++ {
        fmt.Scan(&a[i])
        s += a[i]
    }
    sort.Ints(a[:n])

    s1 = s - a[n-1]
    s2 = s - a[0]

    var stp int
    stp = math.MaxInt
    if((s %  n) == 0) {
        stp = getstp(s / n, 0, n - 1)
    } else {
        stp = min(stp, getstp(s1 / (n - 1), 0, n - 2))
        stp = min(stp, getstp(s1 / (n - 1) + 1, 0, n - 2))
        stp = min(stp, getstp(s2 / (n - 1), 1, n - 1))
        stp = min(stp, getstp(s2 / (n - 1) + 1, 1, n - 1))
    }

    fmt.Print(stp)
}