思路：模拟

显然，要让极差最小，只需要将所有数都靠近平均值就行了。

如果所有数都可以变成平均值，那么极差为0，否则极差为1。

设平均值为$x$(向下取整)，当极差为1时，数组为若干个$x$和若干个$x+1$

代码

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e5+10;
int n;
int a[maxn];

int main() {
    std::ios::sync_with_stdio(false); // 关闭同步，提高C++输入输出效率
    cin >> n; // 输入数组长度
    ll sum = 0;
    for(int i=1;i<=n;++i){
    	cin>>a[i];
    	sum+=a[i];
	}
	ll ans = 0;
	ll ave = sum / n;
	if(ave * n == sum){
		for(int i=1;i<=n;++i){
			if(a[i]<ave){
				ans += ave - a[i];
			}
		}
	}else{
		int cnt = sum - ave * n;
		cnt = n - cnt;
		sort(a+1,a+n+1);
		for(int i=1;i<=n;++i){
			if(i<=cnt && a[i] < ave){
				ans += ave-a[i];
			}else if(i>cnt && a[i] < ave+1){
				ans += ave+1-a[i];
			}
		}
	}
	cout<<ans;
    
    return 0;
}

java

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long[] nums = new long[(int)n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextLong();
            sum += nums[i];
        }

        long avg = sum / n;
        long maxAvg = avg;
        if (sum % n != 0) maxAvg = avg + 1;
        long countMax = 0;
        long countMin = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < avg) countMin += (avg - nums[i]);
            else if (nums[i] > maxAvg) countMax += (nums[i] - maxAvg);
        }
        if (countMax > countMin)
            System.out.println(countMin + (countMax - countMin));
        else {
            System.out.println(countMin);
        }
    }
}

Python

n = int(input())
nums = list(map(int, input().split()))
mean = sum(nums) / n
total1 = 0
total2 = 0
for i in range(n):
    if nums[i] < mean:
        total1 += int(mean - nums[i])
    elif nums[i] > mean:
        total2 += int(nums[i] - mean)
total = max(total1, total2)
print(total)

题目描述

小乖有一个长度为 n 的数组,每次操作可以选择两个下标i和j,将 $a_j$ 减去 1, 将 $a_j$ 加 上1,小乖想知道最少需要多少次操作，可以使数组极差最小。

数组的极差为数组中最大值和最小值的差

输入描述

$第一行输入一个整数 n (2 ≤ n ≤ 10^5), 表示数组的长度$ $第二行输入n个整数 a_1,a_2,...a_n (1 ≤ a_i ≤ 10^9), 代表数组的元素$

输出描述

在一行上输出一个整数,表示最少需要多少次操作。

示例 1

输入

5
1 2 3 4 5

输出

3