题解 | #C. 数组平均#

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

C. 数组平均

这题很有意思，先来看一个显而易见的结论

• k == 1, 则结果为 最大值 - 最小值
• k == n, 则结果必然为 0

如果核心的焦点在于， k在两者之间时，如何求解

一开始猜了一个，从收益最大(差值减少梯度)的角度去贪心，结果WA，而且得分不高

一度没辙，后面仔细分析了下，感觉可以枚举最大的没有被选中的项

如果选中某一个项为最大值，那比它小，而离的越近必然被保留，所以k的选择一定分布在前后缀.

所以思路是

• 排序
• 枚举未被选中的最大值
• 利用前后缀优化加速

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt(), k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);
        if (k == 1) {
            System.out.println(arr[n - 1] - arr[0]);
        } else if (k == n) {
            System.out.println(0);
        } else {
            double ans = arr[n - 1] - arr[0];
            // 前后缀拆解
            long[] suf = new long[n + 1];
            for (int j = n - 1; j >= 0; j--) {
                suf[j] = suf[j + 1] + arr[j];
            }

            long pre = 0;
            // 假设这个元素没被选中
            for (int i = 0; i < n; i++) {
                if (i > k) break;
                long acc = pre + suf[n + i - k];
                double avg = acc * 1.0 / k;
                double m1 = Math.max(avg, arr[n + i - k - 1]);
                double m2 = Math.min(avg, arr[i]);

                ans = Math.min(ans, m1 - m2);
                pre += arr[i];
            }

            System.out.println(ans);
        }
    }

}