选择两个元素,一个加 1,另一个减 1。
小美希望若干次操作后,众数的出现次数尽可能多。你能帮她求出最小的操作次数吗?
众数定义:在一组数据中,出现次数最多的数据,是一组数据中的原数据,而不是相应的次数。 一组数据中的众数不止一个,如数据2、3、-1、2、1、3中,2、3都出现了两次,它们都是这组数据中的众数。
第一行为一个正整数,代表数组的大小。
第二行输入个正整数,代表小美拿到的数组。
一个整数,代表最小的操作次数。
3 1 4 4
2
第一次操作:第一个数加 1,第二个数减 1。第二次操作:第一个数加 1,第三个数减 1。数组变成[3,3,3],众数出现了 3 次。
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); } }
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; } }