ABC313C 解题报告

赛前看到这场 C 的分值直接飙上 \(400\) 就知道不是个善茬。

这道题给了个启发，算是积累个 trick 吧。

题目传送门

简要题意：给定长为 \(n\) 的序列，进行若干次以下操作：每次选定两个整数 \(i\) 和 \(j\)，使得 \(a_{i} \leftarrow a_{i}+1\) 并使得 \(a_{j} \leftarrow a_{j}-1\)，要求最终序列中 \(\max\{a_{i}\}-\min\{a_{i}\} \le 1\)，最小化操作次数。数据范围：\(1 \le n \le 2 \times 10^5\),\(1 \le a_{i} \le 10^9\)。

由于值域很大，所以类似于枚举 \(\max\{a_{i}\}\) 的做法会炸。容易想到一个经典套路：取中位数。但是仔细想想会发现个别极端数据会有很大影响。这时候我们可以类似地想到取平均数。这是可行的，因为相当于取了个中间值。那么 \(\min\{a_{i}\}\)=\(\left\lfloor\dfrac{\sum\limits_{i=1}^n a_{i}}{n}\right\rfloor\)，但是序列总和可能不能整除 \(n\)，因此余数 \(c\) 我们就拆成一个个 \(1\) 使得 \(\max\{a_{i}\}=\min\{a_{i}\}+1\)，这些最大值共有 \(c\) 个，剩下的 \(n-c\) 个便是最小值。最终序列构造完了，我们随便统计一下变换次数即可。时间复杂度 \(O(n)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define LL long long
int n,m,i,j,a[N],s[N];
LL ans,sum,yu;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]),ans+=a[i];
	if(ans%n==0){
		ans/=n;
		for(i=1;i<=n;i++){
			if(a[i]>ans) sum+=a[i]-ans;
		}
		printf("%lld",sum);
		return 0;
	}
	yu=ans%n,ans/=n;
	sort(a+1,a+1+n);
	for(i=1;i<=n-yu;i++) s[i]=ans;
	for(i=n-yu+1;i<=n;i++) s[i]=ans+1;
	for(i=1;i<=n;i++){
		if(a[i]<s[i]) sum+=s[i]-a[i];
	}
	printf("%lld",sum);
	return 0;
}