方法思路

1. 好数组要求：一个特殊元素，其余元素相同
2. 将n-1个元素变成相同值时，选择它们的中位数最优（操作次数最少）
3. 枚举每个位置作为特殊元素，计算剩余元素变为中位数的代价
4. 取所有方案中代价最小值
5. 特殊情况：如果原数组元素全部相同，只需一次操作

代码实现

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextLong();
        }
        
        System.out.println(minOperations(arr, n));
    }
    
    public static long minOperations(long[] arr, int n) {
        // 对数组排序
        Arrays.sort(arr);
        
        // 特殊情况：如果所有元素都相同，需要改变一个元素
        if (arr[0] == arr[n-1]) {
            return 1;  // 只需要改变一个元素
        }
        
        long minOps = Long.MAX_VALUE;
        
        // 尝试每个元素作为"不同的那个"
        for (int i = 0; i < n; i++) {
            // 将剩余元素变成arr[i]左侧的值
            if (i > 0) {
                long leftVal = arr[i-1];
                long leftOps = 0;
                for (int j = 0; j < n; j++) {
                    if (j != i) {
                        leftOps += Math.abs(arr[j] - leftVal);
                    }
                }
                minOps = Math.min(minOps, leftOps);
            }
            
            // 将剩余元素变成arr[i]右侧的值
            if (i < n - 1) {
                long rightVal = arr[i+1];
                long rightOps = 0;
                for (int j = 0; j < n; j++) {
                    if (j != i) {
                        rightOps += Math.abs(arr[j] - rightVal);
                    }
                }
                minOps = Math.min(minOps, rightOps);
            }
        }
        
        // 尝试将n-1个元素变成中位数
        for (int exclude = 0; exclude < n; exclude++) {
            // 创建不包括exclude的新数组
            long[] newArr = new long[n-1];
            int index = 0;
            for (int j = 0; j < n; j++) {
                if (j != exclude) {
                    newArr[index++] = arr[j];
                }
            }
            
            // 找到中位数
            long median = newArr[newArr.length / 2];
            
            // 计算操作次数
            long ops = 0;
            for (int j = 0; j < n; j++) {
                if (j != exclude) {
                    ops += Math.abs(arr[j] - median);
                }
            }
            
            minOps = Math.min(minOps, ops);
        }
        
        return minOps;
    }
}

Python

def min_operations(arr, n):
    # 对数组排序
    arr.sort()
    
    # 特殊情况：如果所有元素都相同，需要改变一个元素
    if arr[0] == arr[n-1]:
        return 1  # 只需要改变一个元素
    
    min_ops = float('inf')
    
    # 尝试每个元素作为"不同的那个"
    for i in range(n):
        # 将剩余元素变成arr[i]左侧的值
        if i > 0:
            left_val = arr[i-1]
            left_ops = 0
            for j in range(n):
                if j != i:
                    left_ops += abs(arr[j] - left_val)
            min_ops = min(min_ops, left_ops)
        
        # 将剩余元素变成arr[i]右侧的值
        if i < n - 1:
            right_val = arr[i+1]
            right_ops = 0
            for j in range(n):
                if j != i:
                    right_ops += abs(arr[j] - right_val)
            min_ops = min(min_ops, right_ops)
    
    # 尝试将n-1个元素变成中位数
    for exclude in range(n):
        # 创建不包括exclude的新数组
        new_arr = [arr[j] for j in range(n) if j != exclude]
        
        # 找到中位数
        median = new_arr[len(new_arr) // 2]
        
        # 计算操作次数
        ops = 0
        for j in range(n):
            if j != exclude:
                ops += abs(arr[j] - median)
        
        min_ops = min(min_ops, ops)
    
    return min_ops

# 读取输入
n = int(input())
arr = list(map(int, input().split()))

# 计算并输出结果
print(min_operations(arr, n))

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

long long minOperations(vector<long long>& arr, int n) {
    // 对数组排序
    sort(arr.begin(), arr.end());
    
    // 特殊情况：如果所有元素都相同，需要改变一个元素
    if (arr[0] == arr[n-1]) {
        return 1;  // 只需要改变一个元素
    }
    
    long long minOps = LLONG_MAX;
    
    // 尝试每个元素作为"不同的那个"
    for (int i = 0; i < n; i++) {
        // 将剩余元素变成arr[i]左侧的值
        if (i > 0) {
            long long leftVal = arr[i-1];
            long long leftOps = 0;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    leftOps += abs(arr[j] - leftVal);
                }
            }
            minOps = min(minOps, leftOps);
        }
        
        // 将剩余元素变成arr[i]右侧的值
        if (i < n - 1) {
            long long rightVal = arr[i+1];
            long long rightOps = 0;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    rightOps += abs(arr[j] - rightVal);
                }
            }
            minOps = min(minOps, rightOps);
        }
    }
    
    // 尝试将n-1个元素变成中位数
    for (int exclude = 0; exclude < n; exclude++) {
        // 创建不包括exclude的新数组
        vector<long long> newArr;
        for (int j = 0; j < n; j++) {
            if (j != exclude) {
                newArr.push_back(arr[j]);
            }
        }
        
        // 找到中位数
        long long median = newArr[newArr.size() / 2];
        
        // 计算操作次数
        long long ops = 0;
        for (int j = 0; j < n; j++) {
            if (j != exclude) {
                ops += abs(arr[j] - median);
            }
        }
        
        minOps = min(minOps, ops);
    }
    
    return minOps;
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    cout << minOperations(arr, n) << endl;
    
    return 0;
}