526互联

Atcoder ABC313_C-Approximate Equalization 2

发布时间 2023-08-07 16:03:44作者: Trilliverse

AT_ABC313_C-Approximate Equalization 2

Description:

  • 给定一个整数序列 \(A=(A_1,A_2,···,A_n)\)，可以做以下操作任意次（可能为0）：选择一个整数对 \((i,j)\) \((1\leq i,j\leq n)\)，使得\(A[i]-\)=\(1\), \(A[j]+\)=\(1\)，求出使得数列 \(A\) 中的 \(max-min \leq 1\) 所需的最少操作次数。

Constraints

  • \(1 \leq n \leq 2 \times 10^5\)
  • \(1 \leq A_i \leq 10^9\)

Analysis:

  • 最容易想到的就是贪心策略，为了让最后的序列尽可能趋同，不妨每次让最大值减小，最小值增大，很明显会超时，故排除。
  • 既然无法通过模拟逐步去逼近，那不妨尝试直接构造终态的数列：我们发现，无论如何操作，由于正负相抵，\(\sum{A_i}\) 恒为定值，故最终必然逼近平均值 \(ave\)，进一步考虑细节，无法整数得到的余数个数即为在平均值基础上\(+1\)的个数，即最终数列由 \(ave\) 和 \(ave+1\)组成。（当然，其分别的个数 \(x\),\(y\) 我们也可以通过方程组求解）

\[\left\{ \begin{aligned} &x+y = n \\ &x\times res+y\times (res+1)=sum=\sum{A_i} \end{aligned} \right. \]

  • 我们已经构造出终态数列 \(B\)，和排序后的 \(A\) 相对应，即可求出总共的加减次数，除以二即为操作次数。
    \(ans =\) \(\frac{\sum_{k=1}^{N} |A_k-B_k|}{2}\)

Solution:

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	ll sum = 0;
	for(int i=0;i<n;i++) {
		cin >> a[i];
		sum += a[i];
	}
	ll ave = sum / n; 
	sort(a.begin(),a.end()); // 排序

	vector<ll> b(n,ave); //初始化构造的序列均为平均值
	
	for(int i=0;i<sum%n;i++) {
		// 进行余数个次的补加1，注意下标运算，从b.end向前操作
		b[n-1-i]++; 
	}
	ll ans = 0;
	for(int i=0;i<n;i++) {
		ans += abs(a[i]-b[i]);
	}
	cout << ans/2 << endl;
	return ;
}