携程第三题记录一下

作者：AFU(OvO)

链接：https://www.nowcoder.com/discuss/1066983

题目大意：给一个数组，考虑将其中的最多k个数剔除数组，并加入这k个数的平均值，问数组中最大值和最小值的差最小能为多少？

public class Q3 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int k = sc.nextInt();

if (n <= k) {

System.out.println(0);

return;

}

double arr[] = new double[n];

for (int i = 0; i < n; i++) {

arr[i] = sc.nextDouble();

}

Arrays.sort(arr);

double leftSum[] = new double[k + 1];

double rightSum[] = new double[k + 1];

for (int i = 1; i <= k; i++) {

leftSum[i] = leftSum[i - 1] + arr[i - 1];

}

for (int i = n - 1; i >= n - k; i--) {

rightSum[n - i] = rightSum[n - i - 1] + arr[i];

}

double ans = arr[n - 1] - arr[0];

for (int i = 0; i <= k; i++) {

int j = k - i;

double avg = (leftSum[i] + rightSum[j]) / (i + j);

double max = Math.max(arr[n - 1 - j], avg);

double min = Math.min(arr[i], avg);

ans = Math.min(ans, max - min);

}

System.out.println(ans);

}

}