题面
核心思想
可以从示例中看出 当 sum / n
能够整除时 我们选择平均数作为众数即可
不能整除时 也就表示着不可能让所有数相同 那么我们可以舍弃掉一个数a
记剩下的数集合为 b
那么当 b
需要 +1 或 -1 后可能会剩下一些数 那么我们可以选择让 a
去执行相反操作从而不影响 b
中剩下的数
比如 a = 1 b = 2 3 3 3 3 3 3 3
,b
中的 2
需要 + 1
,但是 b
中的数不能动了,所以可以和 a
操作。
舍弃一个数后 我们依然需要选择 b
中的平均数作为众数 当不能整除时需考虑 众数 + 1 作为平均数
那么舍弃的数一定是对答案影响最大的数 即最大值or最小值
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
final long MOD = (long) (1e9 + 7);
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
long sum = 0;
for(int i = 0; i < n; i++){
nums[i] = scanner.nextInt();
sum += nums[i];
}
Arrays.sort(nums);
long res = 0;
// 整除的情况
if(sum % n == 0){
//众数等于平均数
long mode = sum / n;
res = calculateOperation(0, n, mode, nums);
}else{
// 舍弃最小值
long curSum = sum - nums[0];
long mode = curSum / (n - 1);
// 如果不能整除 那么 mode + 1 作为众数也是有可能的
long res1 = Math.min(calculateOperation(1, n, mode, nums), calculateOperation(1, n, mode + 1, nums));
// 舍弃最大值
curSum = sum - nums[n - 1];
mode = curSum / (n - 1);
long res2 = Math.min(calculateOperation(0, n - 1, mode, nums), calculateOperation(0, n - 1, mode + 1, nums));
res = Math.min(res1, res2);
}
System.out.println(res);
}
// 计算操作次数
private static long calculateOperation(int start, int end, long mode, int[] nums){
long left = 0, right = 0;
for(int i = start; i < end; i++){
if(nums[i] < mode){
left += Math.abs(nums[i] - mode);
}
else{
right += Math.abs(nums[i] - mode);
}
}
// 相等也就说明能整除 左边的数 + 1 和 右边的数 - 1 刚好能让所有成为众数
if(left == right)
return left;
else // 不能整除 abs(left - right) 多出来的数需要和舍弃的数操作
return Math.max(left, right);
}
}
标签:届秋招,真题,int,美团,nums,long,mode,整除,sum
From: https://www.cnblogs.com/ganyq/p/18125686