526互联

Codeforces Round 730 (Div. 2) B. Customising the Track

发布时间 2023-10-02 18:40:37作者: zsxuan

有 \(n\) 条高速公路，第 \(i\) 条告诉公路上的车流为 \(a_i\) 。现在可以执行以下操作任意次：

  • 将第 \(i\) 条高速公路上的一辆车移到第 \(j\) 条高速公路。

需要求最小的 \(\sum_{i = 1}^{n}\sum_{j=i+1}^{n} |a_i - a_j|\) 。

不难发现可以构造 \(\forall i,j, a_i = a_j\) 使任意两对的贡献为 \(0\) 。

存在余数 \(r\) 的情况下，会得到 \(p+1, p+1, \cdots, p+1, p\cdots,p,p\) 等效于 \(1,1,\cdots,1,0,\cdots,0,0\) 。这种排布可以使得贡献最低，可以通过调整法证明正确性。

答案为 \(r \times (n - r)\) 。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	ll sum = 0;
	for (int i = 1, x; i <= n; i++) std::cin >> x, sum += x;
	int r = sum % n;
	std::cout << 1LL * r* (n - r) << '\n';
}
		                
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}

实际上这题应用的是一个典：
对于数组 \(a\) ，当 \(a\) 的排布为 \(p+1,p+1,\cdots,p+1,p,\cdots,p,p\) 时。\(\sum_{i=1}^{n}\sum_{j=i+1}^{n} a_i - a_j\) 能取到最小且答案为 \(m \times (n - m)\) 。