选择两个元素,一个加 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; }
}