题解 | 小美的数组操作

这题分两种情况，一是可以整出众数为n，不能整除众数为n-1，需要计算最小次数

需要注意，讨论n-1的情况时，根据贪心思想删去最小或最大值，但是要求最优解要考虑减去后的sum/（n-1）的ceil和floor

注意：ceil 时，剩余总和不足，需要补差值，这个差值就是额外操作次数；floor 时，总和已经足够，不需要补。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;
//-1 1 2 2 3 3
//1 1 2 2 3 3
void solve() {
    int n;
    cin>>n;
    vector<int>arr(n+1);
    int sum=0,mx=-1e18,mn=INF;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        sum+=arr[i];
        mx=max(mx,arr[i]);
        mn=min(mn,arr[i]);
    }
    int ans=0;
    if(sum%n==0){
        int sum1=0;
        int t=sum/n;
        for(int i=1;i<=n;i++){
            if(arr[i]>t) sum1+=arr[i]-t;
        }
        ans=sum1;
    }
    else{
        int sum1=sum,sum2=sum,res1=0,res2=0,res3=0,res4=0;
        sum1-=mx,sum2-=mn;
        int t1=sum1/(n-1),t2=sum2/(n-1),t3=(sum1+n-2)/(n-1),t4=(sum2+n-2)/(n-1);
        int d1=(n-1)-(sum1%(n-1)),d2=(n-1)-(sum2%(n-1));
        sort(arr.begin()+1,arr.end());
        for(int i=1;i<n;i++){
            if(arr[i]>t1) res1+=arr[i]-t1;
            if(arr[i]>t3) res3+=arr[i]-t3;
        }
        for(int i=2;i<=n;i++){
            if(arr[i]>t2) res2+=arr[i]-t2;
            if(arr[i]>t4) res4+=arr[i]-t4;
        }
        ans=min(res1,min(res2,min(res3+d1,res4+d2)));
    }
    cout<<ans;
}
signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}