题意

有一个长度为 $n$ 的序列 $a$，每次可以对其中一个数 $+1$，另一个数 $-1$，求最少要多少次操作使得所有数之间的差小于等于 $1$。

思路

因为我们要求所有数差值相等或者相差小于等于 $1$，所以设 $sum$为 $\sum\limits_{i=1}^{n}a_i$，但是可能会有余数的原因，所以有一些数为 $\lfloor\frac{sum}{n}\rfloor$，有一些为 $\lceil\frac{sum}{n}\rceil$。不妨设 $x$ 为前者，$y$ 为后者。

因为 $x \le y$，所以我们只需要使所有大于 $y$ 的数变成 $y$，所有小于 $x$ 的数变成 $x$ 即可。

思路与其他题解几乎大同小异，看看就行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
template<typename P>
inline void read(P &x){
   	P res=0,f=1;
   	char ch=getchar();
   	while(ch<'0' || ch>'9'){
   		if(ch=='-') f=-1;
   		ch=getchar();
   	}
   	while(ch>='0' && ch<='9'){
   		res=res*10+ch-'0';
   		ch=getchar();
	}
	x=res*f;
}
int a[200010];
signed main(){
	int n;
	read(n);
	int sum=0;
	for(int i=1;i<=n;++i){
		read(a[i]);
		sum+=a[i];
	}
	int x=sum/n;
	int y=x+1;
	int ans1=0,ans2=0;
	for(int i=1;i<=n;++i){
		if(a[i]>y) ans1+=a[i]-y;
		else if(a[i]<x) ans2+=x-a[i];
	}
	cout<<max(ans1,ans2)<<endl;
	return 0;
}