首页 > 试题广场 >

小美的数组操作

[编程题]小美的数组操作
  • 热度指数:1779 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小美拿到了一个数组,她每次可以进行如下操作:
选择两个元素,一个加 1,另一个减 1。
小美希望若干次操作后,众数的出现次数尽可能多。你能帮她求出最小的操作次数吗?
众数定义:在一组数据中,出现次数最多的数据,是一组数据中的原数据,而不是相应的次数。 一组数据中的众数不止一个,如数据2、3、-1、2、1、3中,2、3都出现了两次,它们都是这组数据中的众数。

输入描述:
第一行为一个正整数n,代表数组的大小。
第二行输入n个正整数a_i,代表小美拿到的数组。
1\leq n \leq 10^5
1\leq a_i \leq 10^9


输出描述:
一个整数,代表最小的操作次数。
示例1

输入

3
1 4 4

输出

2

说明

第一次操作:第一个数加 1,第二个数减 1。
第二次操作:第一个数加 1,第三个数减 1。
数组变成[3,3,3],众数出现了 3 次。
示例2

输入

3
1 5 5

输出

0

说明

众数出现了 2 次,由于无法再用操作使得众数出现的次数变得更多,所以无需操作。
大体上分两种情况
(1)数组的和(sum),能够整除数组元素的个数(n)。这时,众数就是数组的平均数avg,众数的数量是n。此时计算操作数,那就是每个元素到平均数avg的距离之和除以2,除以二是因为,每一次操作,一个数加一,另一个数减一。因此,计算每个元素到平均数avg的距离之和,相当于把每一次操作算了两遍,后面除以2才是真正的操作数
(2)数组的和(sum),不能整除数组元素的个数(n)。这时,众数的数量是n-1,把数组中的一个数当做垃圾桶(称之为垃圾数),可以把多余的操作都用在垃圾数上,从而让另外n-1个数相同,达到n-1个众数。运用贪心的思想,这个垃圾数一定是数组的最大值或者最小值。

我们以最大值作为垃圾数为例,此时,众数就是剩下n-1个数的平均值(avg),但是有可能不能整除,所以,众数有可能是avg,也有可能是avg+1,(C++默认向下取正)。所以分众数分别是avg和avg+1两种情况讨论,假定众数就是avg,我们现在去计算操作数,定义了两个变量a,b,a用来统计减操作的次数,b用来统计加操作的次数,整体的操作数是max(a,b),a和b的差值就是用在垃圾数上的操作次数。同理,定义c,d去计算众数是avg+1情况下的操作数。最终取min(max(a,b),max(c,d))为最终的操作数。所以,comp函数可以计算数组l到r元素的操作数。

同理,最小值作为垃圾数的操作数也通过comp函数计算。最终的结果就是最大值作为垃圾数,和最小值作为垃圾数两种情况下的操作数的最小值


#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> nums(n);
    for (int i=0; i<n; ++i) {
        cin >> nums[i];
    }
    long long sum = accumulate(nums.begin(), nums.end(), (long long)0);
    if (sum%n==0) {
        long long avg = sum/n;
        long long ans = 0;
        for (auto a:nums) {
            ans += abs(a-avg);
        }
        cout << ans/2 << endl;
        return 0;
    }
    sort(nums.begin(), nums.end());
    function<long long(vector<long long>&, int, int)> comp = [&](vector<long long>& nums, int l, int r) {
        long long tot = 0;
        for (int i=l; i<=r; ++i) {
            tot += nums[i];
        }
        long long avg = tot/(r-l+1);
        long long avg2 = avg+1;
        long long a = 0;
        long long b = 0;
        long long c = 0;
        long long d = 0;
        for (int i=l; i<=r; ++i) {
            if (nums[i]>=avg) a+=nums[i]-avg;
            else b+=avg-nums[i];
            if (nums[i]>=avg2) c+=nums[i]-avg2;
            else d+=avg2-nums[i];
        }
        return min(max(a, b), max(c, d));
    };
    long long res1 = comp(nums, 0, n-2);
    long long res2 = comp(nums, 1, n-1);
    cout << min(res1, res2) << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")


编辑于 2023-08-25 17:20:57 回复(16)
基于@一叶知秋201910082239620 的思路写的Java版

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static long target = -1;
    private static List<Integer> remove = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];
        long sum  = 0L;
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            sum += arr[i];
        }

        // 众数要么是n个,要么是n-1个,
        // 能整除就是n个,不能整除就是n-1个,其中的一个数用来接收多余的操作
        long ans = 0L;
        if (sum % n == 0) {
            long target = sum / n;
            ans = calOps(arr,target,-1);
        } else {
            // 基于贪心的思想,排除的数要么是最大,要么是最小,两者取操作数最小的作为结果
            Arrays.sort(arr);
            ans = Math.min( cal(arr, sum, 0), cal(arr, sum, arr.length - 1));
        }

        System.out.println(ans);
    }

    private static long cal(int[] arr, long sum, int excludeIndex) {
        long ans = 0L;
        sum = sum - arr[excludeIndex];
        long target = sum / (arr.length - 1);
        // avg = sum(n-1个数) / n-1, avg有可能整除,有可能不整除,因此不整除时还要计算众数为avg+1的操作数,取最小
        if( sum % (arr.length -1) == 0){
            return calOps(arr,target,excludeIndex);
        }else{
            return Math.min(calOps(arr,target,excludeIndex),calOps(arr,target+1,excludeIndex));
        }
    }

    /**
     * 计算排除了excludeIndex后,其他数变为target所需要的操作数
     */
    private static long calOps(int[] arr, long target, int excludeIndex) {
        long add = 0L;
        long minus = 0L;
        for (int i = 0; i < arr.length; i++) {
            if (i == excludeIndex) continue;
            if (target - arr[i] > 0) {
                // 加的操作数
                add += target - arr[i];
            } else {
                // 减的操作数
                minus += arr[i] - target;
            }
        }
        // 如果不用排除,则add==minus,
        // 否则|add-minus|多余的操作则作用在excludeIndex的数上
        return Math.max(add, minus);
    }

}
编辑于 2024-01-30 18:52:17 回复(0)
#include <iostream>
#include<map>
#include<climits>
#include<cmath>
using namespace std;

int main() {
   /*
    思路:
    加一减一,貌似意味着有一串数字,如果个数为n且其和能够被n整除,就可以变为n个一样的数
    基于此:
    1求出所有数的和
    2.若和能够被n整除则可假设目标众数为sum/n,求操作次数
      若和不能被整除,为保证最小的操作次数,必须将变化最多的数剔除,也就是数组中最大或最小的元素。
        目标众数设置为 (sum - (max or min) ) / n - 1 或其+1,具体选择四舍五入;求操作次数
    3.操作次数的求法,看数与目标众数的绝对值,大于1点就一次。最后除以2
     
   
   */

    long long res = 0;
    long long sum = 0;

    //元素个数
    long long n = 0;
    cin>>n;


    //<数字,次数>
    map<long,long> dgCount;

    long long maxNum = LONG_MIN;
    long long minNum = LONG_MAX;

    long long tempNum;
    for(long long i = 0; i < n; i++)
    {
        cin >> tempNum;
        //出现次数加一
        dgCount[tempNum] += 1;

        //求和
        sum += tempNum;

        if(maxNum < tempNum)
        {
            maxNum = tempNum;
        }
        if(minNum > tempNum)
        {
            minNum = tempNum;
        }
    }

    long long target = 0;

    //和能够被n整除的情况
    if (sum % n == 0) {
        target = sum / n;
        for(auto it:dgCount)
        {
            
            res += abs(it.first-target)*it.second;
            
        }
        cout<< res / 2;
        return 0;
    }
    
    //假定最大数需要最多操作次数
    long long maxRes = 0;

    //剔除一个最大数
    dgCount[maxNum] --;
    
    //开始计算目标众数
    target = round((sum - maxNum) / ((n-1)*1.0));
    
    //求操作次数
    for(auto it:dgCount)
    {
        
        maxRes += abs(it.first-target)*it.second;
        
    }
    //最终答案需要除以2,将多余变化再加一次
    maxRes += abs(sum - maxNum - target * (n-1));

    
    //恢复
    dgCount[maxNum]++;
    
    
    long long minRes = 0;
    
    dgCount[minNum] --;
    
    target = round((sum - minNum) / ((n-1)*1.0));
  
    for(auto it:dgCount)
    {
        
        minRes += abs(it.first-target)*it.second;
        
    }
    minRes += abs(sum - minNum - target * (n-1));

    cout<< (minRes<maxRes?minRes:maxRes)/2;

    return 0;

}
// 64 位输出请用 printf("%lld")
发表于 2023-08-31 12:04:27 回复(0)
天呐 天呐  这道题卡了我一天,终于30个全部通过了!!感谢评论区的大佬,参照了评论的思路

Scanner sc = new Scanner(System.in);
long leastTimes = 0; //最终结果
int n = 0; //数组个数
n = sc.nextInt();
long[] arr = new long[n];
int t = 0;
//输入该数组
while (t < n) {
    arr[t++] = sc.nextInt();
}
//求数组之和
long sum = 0;
for (long j : arr) {
    sum += j;
}
long avg = sum / arr.length;//平均数
//平均数为整数
if (sum % arr.length == 0) {
    for (int i = 0; i < arr.length; i++) {
        leastTimes += Math.abs(arr[i] - avg);
    }
    System.out.println(leastTimes / 2);
    return;
}
//平均数除不清
else {
    sum = 0;
    Arrays.sort(arr);
    long[] newArr = new long[arr.length - 1]; //去掉垃圾数之后的数组
    long leastTimes2 = 0;
    //取最小数为垃圾数
    for (int i = 0; i < arr.length - 1; i++) {
        newArr[i] = arr[i + 1];
        sum += arr[i + 1];
    }
    avg = sum / newArr.length;//新数组的平均数
    //新数组平均数为整数
    if (sum % (newArr.length) == 0) {
        //各个数据到平均数的距离之和除以2
        for (long j : newArr) {
            leastTimes += Math.abs(avg - j) ;
        }
        leastTimes /= 2;
    } else {
        long plus = 0;
        long minus = 0;
        //众数为avg
        for (int i = 0; i < newArr.length; i++) {
            //加操作数次数
            if (avg > newArr[i]) {
                plus += avg - newArr[i];
            }
            //减操作数次数
            else {
                minus += newArr[i] - avg;
            }
        }
        leastTimes = Math.max(plus, minus);

        plus = 0;
        minus = 0;
        //众数为avg+1
        avg+=1;
        for (int i = 0; i < newArr.length; i++) {
            //加操作数次数
            if (avg > newArr[i]) {
                plus += avg - newArr[i];
            }
            //减操作数次数
            else {
                minus += newArr[i] - avg;
            }
        }
        leastTimes = Math.min(leastTimes, Math.max(plus, minus));
    }
    sum=0;
    //取最大数为垃圾数
    for (int i = 0; i < arr.length - 1; i++) {
        newArr[i] = arr[i];
        sum += arr[i];
    }
    avg = sum / newArr.length;//新数组的平均数
    //新数组平均数为整数
    if (sum % (newArr.length) == 0) {
        //各个数据到平均数的距离之和除以2
        for (long j : newArr) {
            leastTimes2 += Math.abs(avg - j) ;
        }
        leastTimes2 /= 2;
    } else {
        long plus = 0;
        long minus = 0;
        //众数为avg
        for (int i = 0; i < newArr.length; i++) {
            //加操作数次数
            if (avg > newArr[i]) {
                plus += avg - newArr[i];
            }
            //减操作数次数
            else {
                minus += newArr[i] - avg;
            }
        }
        leastTimes2 = Math.max(plus, minus);

        plus = 0;
        minus = 0;
        //众数为avg+1
        avg+=1;
        for (int i = 0; i < newArr.length; i++) {
            //加操作数次数
            if (avg > newArr[i]) {
                plus += avg - newArr[i];
            }
            //减操作数次数
            else {
                minus += newArr[i] - avg;
            }
        }
        leastTimes2 = Math.min(leastTimes2, Math.max(plus, minus));
    }


    System.out.print(Math.min(leastTimes, leastTimes2));
}

发表于 2023-10-07 22:33:48 回复(0)
def back(ls, index):
    ls.pop(index)
    n = len(ls)
    avg_1 = round(sum(ls) / n)
    high = 0
    for num in ls:
        if num > avg_1:
            high += (num - avg_1)
    high_2 = 0
    for num in ls:
        if num < avg_1:
            high_2 += abs(num - avg_1)
    high = max(high_2, high)
    return high


def max_zhongshu(n, ls):
    if sum(ls)%n==0:
        avg = sum(ls)//n
        high = 0
        for num in ls:
            if num>avg:
                high+=(num-avg)
        print(high)
    else:
        max_num = max(ls)
        max_index = ls.index(max_num)

        min_num = min(ls)
        min_index = ls.index(min_num)

        ls_copy = ls.copy()
        a = back(ls, max_index)
        b = back(ls_copy, min_index)
        print(min(a, b))

发表于 2023-10-08 22:40:28 回复(0)
import java.util.*;
import java.io.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        String[] str = bf.readLine().split(" ");
        long[] nums = new long[n];
        long sum=0;
        for(int i=0;i<n;i++){
            nums[i]=Long.parseLong(str[i]);
            sum+=nums[i];
        }
        //System.out.println("sum="+sum+",sum%n="+(sum%n));
        if((sum%n)==0){
            long avg = sum/n;
            long step =0;
            for(int i=0;i<n;i++){
                if(nums[i]>avg){
                    step+=nums[i]-avg;
                }
            }
            System.out.println(step);
            return;
        }
        Arrays.sort(nums);

        long res =Long.MAX_VALUE;
        long removeBigSum = sum-nums[n-1];
        long removeSmallSum = sum-nums[0];

        //去掉最大值,剩下的值取平均作为最终的众数。如果剩下的平均不是整数,取两边相邻的整数分别计算
        //如平均值为23.1,那么就计算23和24两种情况
        long bigRes = Long.MAX_VALUE;
        long avg = removeBigSum/(n-1);
        long step =0;
        for(int i=0;i<n-1;i++){
            if(nums[i]>avg){
                step+=nums[i]-avg;
            }
        }
        //System.out.println("removeBigSum="+removeBigSum+",step="+step);
        bigRes=Math.min(bigRes, step);


        if((removeBigSum%(n-1)) != 0){
            step =0;
            avg = (removeBigSum/(n-1))+1;
            for(int i=0;i<n-1;i++){
                if(nums[i]<avg){
                    step+=avg-nums[i];
                }
            }
            //System.out.println("removeBigSum="+removeBigSum+",step="+step);
            bigRes=Math.min(bigRes, step);
        }

        //去掉最小值,剩下的值取平均作为最终的众数。如果剩下的平均不是整数,取两边相邻的整数分别计算
        //如平均值为23.1,那么就计算23和24两种情况
        long smallRes = Long.MAX_VALUE;
        avg = removeSmallSum/(n-1);
        step =0;
        for(int i=1;i<n;i++){
            if(nums[i]>avg){
                step+=nums[i]-avg;
            }
        }
        //System.out.println("removeSmallSum="+removeSmallSum+",step="+step);
        smallRes=Math.min(smallRes, step);

        if((removeSmallSum%(n-1)) != 0){
            step =0;
            avg = (removeSmallSum/(n-1))+1;
            for(int i=1;i<n;i++){
                if(nums[i]<avg){
                    step+=avg-nums[i];
                }
            }
            //System.out.println("removeSmallSum="+removeSmallSum+",step="+step);
            smallRes=Math.min(smallRes, step);
        }


        res = Math.min(smallRes, bigRes);
        System.out.println(res);
    }
}

发表于 2024-09-01 17:28:59 回复(0)
public class m2024Code2Version2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        //如果 sum / n 可以整除,说明平均数可以作为众数

        // 尽可能在数组中找到可以凑成 sum / 个数 满足整除的子集 数组

        int n = in.nextInt();
        long[] nums = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];
        }

        long count = 0;
        if (sum % n == 0) { //可以整除的情况
            long avg = sum / n; //平均数
            for (int i = 0; i < n; i++) {
                count += Math.abs(nums[i] - avg);
            }
            System.out.print(count / 2);
            return;
        }

        // 如果不能整除,说明不能使众数出现n次,  贪心思想,排除原数组的最大值或最小值,计算剩下的n-1个元素能否被均分,
        // 能均分众数就是 sum_part / (n -1)    不能均分 一种也是 sum_part / (n-1)向下取整,  或者  sum_part / (n-1)向下取整 + 1

// 解释一下  3 3 3 4 9 ; 原数组不能整除,选择9作为垃圾数,  3 + 3 + 3 + 4  / 4 = 3.25  一种众数是向下取整3  一种众数是 3 + 1 = 4   明显3,即向下取整
//          3 3 3 1 9 ;                选择9作为垃圾数    3 + 3 + 3 + 1  / 4 = 2.5  一种总数是向下取整2  一种众数是 2 + 1 = 3   明显3,即取整后+1
        //                                               3 + 3 + 3 + 2  / 4 = 2.75                              2 + 1 = 3

        // 新思路:能否不针对两种 avg计算,  3.25 -> 0.25 < 0.5, 向下取整,调整次数更少    2.5 -> 0.5 >=0.5 适合+1
        //  四舍五入

        Arrays.sort(nums); //排序

        long res1 = compare(0, nums, sum);
        long res2 = compare(nums.length - 1, nums, sum);

        System.out.print(Math.min(res1, res2));

    }

    private static long compare(int del, long[] nums, long sum) {
        sum -= nums[del]; // 移除最大或最小元素

        long avg = Math.round( (double) sum / (nums.length - 1) ); // 四舍五入
        // long avg2 = sum / (nums.length - 1) + 1;

        // System.out.println("avg = " + avg);

        long add = 0;
        long minus = 0;

        // long add2 = 0;
        // long minus2 = 0;

        if (del == 0) {
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > avg) {
                    minus += nums[i] - avg;
                } else {
                    add += avg - nums[i];
                }

                // if (nums[i] > avg2) {
                //     minus2 += nums[i] - avg2;
                // } else {
                //     add2 += avg2 - nums[i];
                // }
            }
        } else {
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] > avg) {
                    minus += nums[i] - avg;
                } else {
                    add += avg - nums[i];
                }

                // if (nums[i] > avg2) {
                //     minus2 += nums[i] - avg2;

                // } else {
                //     add2 += avg2 - nums[i];
                // }
            }
        }


        // return Math.min(Math.max(add, minus), Math.max(add2, minus2));
        return Math.max(add, minus);
    }
}

发表于 2024-04-13 09:44:11 回复(0)
参考评论第一的思路。
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long sum = 0;
        long[] a = new long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextLong();
            sum += a[i];
        }
        Arrays.sort(a);
        if (sum % n == 0) {
            long avg = sum / n;
            System.out.println(cp(a, avg));
        } else {
            // 将最大值作为垃圾数
            long s = sum - a[n - 1];
            long[] t = new long[n - 1];
            System.arraycopy(a, 0, t, 0, n - 1);
            long ans1 = cp(t, s / (n - 1));
            long ans2 = cp(t, s / (n - 1) + 1);
            // 将最小值作为垃圾数
            s = sum - a[0];
            System.arraycopy(a, 1, t, 0, n - 1);
            long ans3 = cp(t, s / (n - 1));
            long ans4 = cp(t, s / (n - 1) + 1);
            long ans = Math.min(Math.min(ans1, ans2), Math.min(ans3, ans4));
            System.out.println(ans);
        }
    }

    static long cp(long[] a, long avg) {
        long ans1 = 0, ans2 = 0;
        for (long x: a) {
            if (x > avg) ans1 += x - avg;
            else ans2 += avg - x;
        }
        return Math.max(ans1, ans2);
    }
}


编辑于 2023-12-26 20:56:48 回复(0)
package zhongShuCaoZuoShu;  import java.util.Arrays; import java.util.Scanner;  import static java.lang.Math.abs;  public class Main { public static void main(String[] args) {
        Scanner in = new Scanner(System.in); int N = in.nextInt();  int[] arr = new int[N];  // 和  // 目标众数  // 操作次数  int sum = 0; int target = 0;  // int count=0;  for(int i =0;i;i++){
            arr[i]=in.nextInt();  sum += arr[i];  } // System.out.println(sum); // 一串数据怎么知道会不会出现更多的众数呢  if(arr.length==0 || arr==null){
            System.out.print(0);  }
        Arrays.sort(arr);  System.out.print(findArr(arr,sum,N));  } public static int findArr(int[] arr,int sum,int N){ int target =sum/N; int count = 0;  // 直观上来说,如果一串数据能够都划为众数,说明他们的和能够被位数整除,例如1 4 4,和为9,位3,整除  // 2 3 5 6 --> 4 4 4 4 则16除4位,整除  // 极端情况,一组数据都能划为众数  if(sum%N==0){ // 整除说明全部众数  for(int i = 0;i;i++){
                count += abs(target-arr[i]);  }
            count /= 2;  // System.out.println(target);  }else{ // 如果不能我们就刨除最大或最小的值  int[] newArr = new int[N-1];  if(arr[N-1]-target>target-arr[0]){ // 大的离得更远  // 退掉最高位  for(int i =0;i1;i++){
                    newArr[i]=arr[i];  } //控制sum值  sum=sum-arr[N-1];  }else{ // 小的离得远  // 退掉小位  for(int i =0;i1;i++){
                    newArr[i]=arr[i+1];  } //控制sum值   sum=sum-arr[0];  } //让N-1长度减少  N=N-1;  findArr(newArr,sum,N);  } return count;  }
}
发表于 2023-10-06 20:50:55 回复(0)
from itertools import accumulate
 
n = int(input())
a = [int(c) for c in input().split()]
 
a.sort()
sum_ = sum(a)
if sum_ % n == 0:
    res = 0
    avg = sum_ // n
    for i in a:
        res += abs(avg - i)
    res //= 2
    print(res)
else:
    nums1 = a[1:]
    nums2 = a[:-1]
 
    def cal(nums):
        sum_ = sum(nums)
        avg = int(sum_ / len(nums) + 0.5)
        x,y = 0, 0
        for num in nums:
            if num >= avg: x+= num -avg
            else: y+= avg - num
        return max(x,y)
 
    print(min(cal(nums1), cal(nums2)))
发表于 2023-09-24 20:56:06 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        // 和
        // 目标众数
        // 操作次数
        int sum = 0;
        int target = 0;
        // int count=0;
        for(int i =0;i<N;i++){
            arr[i]=in.nextInt();
            sum+=arr[i];
        }
        // System.out.println(sum);
        // 一串数据怎么知道会不会出现更多的众数呢
        if(arr.length==0 || arr==null){
            System.out.print(0);
        }
        Arrays.sort(arr);
        System.out.print(findArr(arr,sum,N));
    }
    public static int findArr(int[] arr,int sum,int N){
        int target =sum/N; 
        int count = 0;
        // 直观上来说,如果一串数据能够都划为众数,说明他们的和能够被位数整除,例如1 4 4,和为9,位3,整除
        // 2 3 5 6 --> 4 4 4 4 则16除4位,整除
        // 极端情况,一组数据都能划为众数
        if(sum%N==0){
            // 整除说明全部众数
            for(int i = 0;i<N/2;i++){
                count += target-arr[i];
            }
            // System.out.println(target);
        }else{
            // 如果不能我们就刨除最大或最小的值
            int[] newArr = new int[N-1];
            if(arr[N-1]-target>target-arr[0]){
                // 大的离得更远
                // 退掉最高位
                for(int i =0;i<N-1;i++){
                    newArr[i]=arr[i];
                }
                //控制sum值
                sum=sum-arr[N-1];
            }else{
                // 小的离得远
                // 退掉小位
                for(int i =0;i<N-1;i++){
                    newArr[i]=arr[i+1];
                }
                //控制sum值
                sum=sum-arr[0];
            }
            //让N-1长度减少
            N=N-1;
            findArr(newArr,sum,N);
        }
        return count;
    }
}
能不能帮哥们看看哪里没考虑到吗
发表于 2023-09-07 17:35:02 回复(1)
//看完了思路还是写了一小时...
#include <iostream>
#include <locale>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
typedef long long LL;
LL q[100010];
LL method(int l,int r,LL target)//区间[l,r]的众数为target,返回操作次数
{
    LL res=0;
    for(int i=l;i<=r;i++)
        res+=abs(q[i]-target);
    return res;
}
int main() {
    int n;
    cin>>n;
    LL sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
        sum+=q[i];
    }
    if(sum%n==0)
    {
        cout<<method(0,n-1,sum/n)/2;
        return 0;
    }
    //如果不能整除,尝试删掉最大值或者最小值
    sort(q,q+n);
    //删掉最大值
    LL tmp_sum=sum-q[n-1];
    LL target=tmp_sum/(n-1);
    LL max_res_1=method(0,n-2,target)+abs(tmp_sum-(n-1)*target);
    LL max_res_2=method(0,n-2,target+1)+abs(tmp_sum-(n-1)*(target+1));
    LL max_res=min(max_res_1,max_res_2);
    //删掉最小值
    tmp_sum=sum-q[0];target=tmp_sum/(n-1);
    LL min_res_1=method(1,n-1,target)+abs(tmp_sum-(n-1)*target);
    LL min_res_2=method(1,n-1,target+1)+abs(tmp_sum-(n-1)*(target+1));
    LL min_res=min(min_res_1,min_res_2);
    cout<<min(min_res,max_res)/2;
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2023-09-07 15:42:00 回复(0)
用Python做的,27/30的通过率,来个大佬看看哪出问题了
whileTrue:
    try:
        sum = 0
        ave = 0
        ave1 = 0
        ave2 = 0
         
        n = int(input())
        a = list(map(int,input().split()))
        a = sorted(a)
        fori in range(n):
            sum += a[i]
        ifsum % n == 0:
            fori in range(n):
                ave += abs(sum / n - a[i])
            print(int(ave / 2))
        elif sum - a[0] * n > a[-1] * n - sum:
            sum -= a[0]
            ifsum / (n - 1) - sum // (n - 1) > 0.5:
                med = sum // (n - 1) + 1
            else:
                med = sum // (n - 1)
            fori in range(n - 1):
                ifa[i + 1] < med:
                    ans1 = med - a[i + 1]
                    ave1 += ans1
                else:
                    ans2 = a[i + 1] - med               
                    ave2 += ans2
            print(int(((ave1 + ave2)-abs(ave1 - ave2)) / 2+ abs(ave1 - ave2)))
        else:
            sum -= a[-1]
            ifsum / (n - 1) - sum // (n - 1) > 0.5:
                med = sum // (n - 1) + 1
            else:
                med = sum // (n - 1)
            fori in range(n - 1):
                ifa[i] < med:
                    ans1 = med - a[i]
                    ave1 += ans1
                else:
                    ans2 = a[i] - med               
                    ave2 += ans2
            print(int(((ave1 + ave2)-abs(ave1 - ave2)) / 2+ abs(ave1 - ave2)))
    except:
        break
发表于 2023-09-06 23:53:32 回复(0)
#include <stdio.h>
#include <stdlib.h>

static int cmp_int(const void *p1, const void *p2)
{
    return *(long *)p1 - *(long *)p2;
}

// long max_num = 0, min_num = __INT64_MAX__;
long find_cnt(long *nums, int size, long avg, int flag)
{
    long cnt_add = 0;
    long cnt_delete = 0;

    for (int i = 0; i < size; i++)
    {
        if (nums[i] < avg) {
            cnt_add += avg - nums[i];
        } else if (nums[i] > avg) {
            cnt_delete += nums[i] - avg;
        }
    }

    if (flag == 1) {
        if (cnt_add > cnt_delete) {
            cnt_add -= (avg - nums[0]);
        } else {
            cnt_delete -= (nums[size - 1] - avg);
        }
    }
    return cnt_add > cnt_delete? cnt_add: cnt_delete;
}

int main(int argc, char *argv[])
{
    int size = 0;
    scanf("%d", &size);

    long nums[size];
    long sum = 0;
   
    for (int i = 0; i < size; i++)
    {
        scanf("%ld", &nums[i]);
        sum += nums[i];
        // if (nums[i] < min_num) {
        //     min_num = nums[i];
        // }
        // if (nums[i] > max_num) {
        //     max_num = nums[i];
        // }
    }
    qsort(nums, size, sizeof(long), cmp_int);
    long result = 0;
    if (sum % size == 0) {
        result = find_cnt(nums, size, sum / size, 0);
    } else {
        long select_nums[4];
        select_nums[0] = (sum - nums[0]) / (size - 1);
        select_nums[1] = select_nums[0] + 1;
        select_nums[2] = (sum - nums[size - 1]) / (size - 1);
        select_nums[3] = select_nums[2] + 1;

        long tmp = 0;
        result = find_cnt(nums, size, select_nums[0], 1);
        for (int i = 1; i < 4; i++)
        {
            tmp = find_cnt(nums, size, select_nums[i], 1);
            if (tmp < result) {
                result = tmp;
            }
        }
    }

    printf("%ld\r\n", result);
    return 0;
}
发表于 2023-08-29 15:24:11 回复(0)
蹲一个题解
发表于 2023-08-24 14:10:05 回复(3)