首页 > 试题广场 >

小美的数组操作

[编程题]小美的数组操作
  • 热度指数:1780 时间限制: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 次,由于无法再用操作使得众数出现的次数变得更多,所以无需操作。
参考评论第一的思路。
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)