小美的数组操作【牛客tracker 每日一题】

小美的数组操作

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小美拿到了一个数组，她每次可以进行如下操作：
选择两个元素，一个加1 11，另一个减1 11。

小美希望若干次操作后，众数的出现次数尽可能多。你能帮她求出最小的操作次数吗？

众数定义：在一组数据中，出现次数最多的数据，是一组数据中的原数据，而不是相应的次数。 一组数据中的众数不止一个，如数据2 、 3 、 − 1 、 2 、 1 、 3 2、3、-1、2、1、32、3、−1、2、1、3中，2 、 3 2、32、3都出现了两次，它们都是这组数据中的众数。

输入描述：

第一行为一个正整数n nn，代表数组的大小。
第二行输入n nn个正整数a i a_iai​​，代表小美拿到的数组。
1 ≤ n ≤ 10 5 1≤n≤10^51≤n≤105
1 ≤ a i ≤ 10 9 1≤a_i≤10^91≤ai​≤109

输出描述：

一个整数，代表最小的操作次数。

示例1

输入：

3 1 4 4

输出：

2

说明：

第一次操作：第一个数加1 11，第二个数减1 11。
第二次操作：第一个数加1 11，第三个数减1 11。
数组变成[ 3 , 3 , 3 ] [3,3,3][3,3,3]，众数出现了3 33次。

示例2

输入：

3 1 5 5

输出：

0

说明：

众数出现了2 22次，由于无法再用操作使得众数出现的次数变得更多，所以无需操作。

解题思路

本题依托数组总和守恒的核心特性（每次操作一增一减不改变总和），明确众数能达到的最大次数为数组长度n nn（总和可均分时）或n − 1 n-1n−1（总和不可均分时），先判断数组总和是否能被n nn整除，若可以则直接计算所有元素转为该平均值的总操作次数作为答案；若不可均分则无法让全部元素相同，进一步剔除数组中的最大值、最小值分别计算剩余n − 1 n-1n−1个元素总和的均分候选值，结合余数核算两种目标取值的操作成本，最终取所有候选方案中的最小操作次数，高效适配n ≤ 10 5 n≤10⁵n≤105的数据规模，精准得到满足众数次数最大化的最小操作代价。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e6+10;intmain(){ll n;cin>>n;ll v[n];ll sum=0;ll m=0,M=0;for(ll i=0;i<n;i++){cin>>v[i];sum+=v[i];if(v[i]>v[M])M=i;if(v[i]<v[m])m=i;}function<ll(ll,ll)>cal=[&](ll p,ll idx){ll res=0;for(ll i=0;i<n;i++){if(i==idx)continue;if(v[i]>p)res+=v[i]-p;}returnres;};ll ans=0;if(sum%n==0)ans=cal(sum/n,-1);else{ll k=(sum-v[M])%(n-1);ans=cal((sum-v[M])/(n-1),M);ans=min(ans,cal((sum-v[M])/(n-1)+1,M)+n-1-k);k=(sum-v[m])%(n-1);ans=min(ans,cal((sum-v[m])/(n-1),m));ans=min(ans,cal((sum-v[m])/(n-1)+1,m)+n-1-k);}cout<<ans<<endl;return0;}