题解：中位数贪心+分类讨论

首先考虑一种特殊情况：数组中所有元素都相等，那么对任何一个元素进行+1或者-1操作都可以，因此对应的代价就是1

如果数组中元素不相等，那么最优解应该是操作完之后，数组中的最大值/最小值与数组中剩下的n-1个数不同，因此直接把数组排序之后，分类讨论，按照中位数贪心求一下这两种情况的答案，最后取一个最小值即可

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1E5+10;
int w[N],n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>w[i];
    sort(w,w+n);
    if(w[0]==w[n-1]){
        puts("1");
        return 0;
    }
    ll s1=0,s2=0;
    int m1=w[(n-1)/2],m2=w[(n+1)/2];  //分别计算去除第一个数字和最后一个数字的最小操作次数
    for(int i=0;i<n-1;i++){
        s1+=abs(m1-w[i]);
    }
    for(int i=1;i<n;i++){
        s2+=abs(m2-w[i]);
    }
    ll res=min(s1,s2);
    cout<<res<<endl;
    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] w = new int[n];

        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }

        Arrays.sort(w);

        if (w[0] == w[n - 1]) {
            System.out.println("1");
            return;
        }

        long s1 = 0, s2 = 0;
        int m1 = w[(n - 1) / 2];
        int m2 = w[(n + 1) / 2];

        for (int i = 0; i < n - 1; i++) {
            s1 += Math.abs(m1 - w[i]);
        }

        for (int i = 1; i < n; i++) {
            s2 += Math.abs(m2 - w[i]);
        }

        long res = Math.min(s1, s2);
        System.out.println(res);
    }
}

Python3

n = int(input())
w = list(map(int, input().split()))
w.sort()

if w[0] == w[-1]:
    print("1")
else:
    s1, s2 = 0, 0
    m1 = w[(n - 1) // 2]
    m2 = w[(n + 1) // 2]

    for i in range(n - 1):
        s1 += abs(m1 - w[i])

    for i in range(1, n):
        s2 += abs(m2 - w[i])

    res = min(s1, s2)
    print(res)

题目内容

小红有一个长度为 $n$ 的数组 $a$ 。但是他觉得一般的数组很不优雅。

对于小红来说，一个长度为 $n$ 的数组，有 $n-1$ 个数相同，有 $1$ 个数与这 $n-1$ 个数不同，则这个数组是优雅的。

每次操作可以使得数组中一个数的值加 $1$ 或减 $1$ 。

现在，小红想问你，至少要多少次操作，才能使得数组变得优雅。

输入描述

第一行，一个正整数$n(1\leq n\leq 10^5)$，表示数组的大小。

第二行，$n$个正整数$a_i(1\leq a_i\leq 10^9)$，表示数组的 $n$ 个元素。

输出描述

一个整数，表示使得数组变得优雅的最少操作次数。

样例

输入

4
1 2 3 4

输出

2

说明

将 $a[0]=1$ 通过一次加操作修改为 $2$，将 $a[2]=3$ 通过一次减法操作修改为 $2$ 。

最终 $2$ 次操作数组变为 2 2 2 4 。