题解 | #C. 数组平均#

数组平均

https://ac.nowcoder.com/acm/contest/68338/C

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

C. 数组平均

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

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

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

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

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

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

alt

所以思路是

  • 排序
  • 枚举未被选中的最大值
  • 利用前后缀优化加速
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);
        }
    }

}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
嵐jlu:我是山川🐔里🐔🧱的,阿里系简历全过; 你这简历一看就还是半成品啊,没有荣誉经历奖项什么的吗?
投递阿里巴巴集团等公司10个岗位
点赞 评论 收藏
分享
评论
5
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务