有 \(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)\) 。
#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)\) 。