CF1543B

MikeC · 2021-07-19 16:25:04 · 题解

分析

要求数列和不变，对数列进行任意操作，求出数列中任意两个数差值的绝对值的和的最小值。我们自然可以想到尽可能地让数值均分，均分过后的数列一定只会有 1 种或 2 种数值，作差即可得到答案。

对于作差，我们也可以进行推导优化。假设均分过后的数列有 2 种数值，那么较大数值的个数为 \sum_{i=1}^{n} a[i]\;\bmod\; n ，因为只存在 2 种数值，所以较大数值与较小数值作差的绝对值一定为 1，那么我们的答案就是较大数值的个数乘较小数值的个数即 [n\;\cdot\;(\sum_{i=1}^{n} a[i])\;\bmod\; n]-[(\sum_{i=1}^{n} a[i])\;\bmod\; n]^2

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[200001];
int sum,op;
signed main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        sum=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            sum+=a[i];
        }
        op=sum%n;
        printf("%lld\n",(n-op)*op);
    }
}