当前位置: 首页 > article >正文

二分+前缀和/滑动窗口——成绩统计

成绩统计(二分+前缀和/滑动窗口)24年省赛

题目分析:

定位关键词——“至少要检查多少个人的成绩,才有可能选出 k 名同学,他们的方差小于一个给定的值 T”,也就是满足条件的最小值,可以考虑用二分。但是他需要可以二分,也就是单调性或者二段性。每次选择都是选择前x个数,然后在这前x个数里面找到一组个数为k的数,他们的方差满足条件,如果x可以找到,那么x继续增大也可以找到,因为增大后的x是包含了增大前的x的。举个例子,假设x=5。在a[1],a[2],a[3],a[4],a[5]中,我们可以找到a[2],a[3],a[5]满足方差小于T,那么当x=8时,对于a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]也一定存在a[2],a[3],a[5]满足方差小于T,因此具有单调性,也就是小的值满足条件,大的值也一定满足条件。

接下来考虑二分过程。

第一阶段二段性分析

当我检查了前mid个同学的成绩之后,如果可以找到一组数,个数为k,且方差小于T,那么我会尝试找更小的值是不是也满足条件,所以向左边走,即

if (check(mid)) {r = mid;} //因为mid是符合条件的,所以我要留着它,而不是l=mid+1

当我检查了前mid个同学的成绩之后,如果不可以找到一组数,个数为k,且方差小于T,那么我只能找更大的值,所以向右边走,即

else { l = mid + 1; }//因为mid是不符合条件的,所以我不要留着它,而不是r=mid

综上该题满足二段性,可以用二分,二分的板子就不说了,接下来说一下check函数如何写。

第二阶段写check函数

check(mid)要实现的作用是当我知道了前mid个学生的成绩后,能否快速找出k名同学,使得他们的方差小于T。如果不能则返回false,否则返回true。我们希望选出来的k名同学的方差尽可能小,方差衡量的是数据之间的差值,自然要选择数据相近的k个值,所以我们可以对原始数据进行排序,然后选择连续的k个值就可以了。但是怎么快速计算选出来的k个值的方差呢?这就要根据方差公式了。

image-20241204170908628

对于 ∑ i = 1 k v i 2 \sum_{i=1}^k{v_i^2} i=1kvi2 ∑ i = 1 k v i \sum_{i=1}^k{v_i} i=1kvi,我们可以通过前缀和、前缀平方和或者滑动窗口的形式快速得到。而对于剩余的可以直接计算得出。所以代码如下,

static boolean check(int mid) {
        for (int i = 1; i <= mid; i++)
            b[i] = a[i];
        Arrays.sort(b, 1, mid + 1);//排序
        long v2 = 0, v = 0;
        for (int i = 1; i < k; i++) {//预处理数组b的前k-1项相关数据
            v2 += 1L * b[i] * b[i];//求平方和
            v += b[i];//求和
        }
        for (int i = k; i <= mid; i++) {
            v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];//类似滑动窗口,加上当前值,去掉已经滑出去的值
            v += b[i] - b[i - k];//类似滑动窗口,加上当前值,去掉已经滑出去的值
            double avg = 1.0 * v / k;//得到平均值
            if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
                return true;
        }
        return false;
    }

刚刚的代码采用的是滑动窗口的思路,下面的代码使用的是前缀和的思路,

static boolean check(int mid) {
        for (int i = 1; i <= mid; i++)
            b[i] = a[i];
        Arrays.sort(b, 1, mid + 1);
        long[] sum_v2 = new long[mid+1], sum_v = new long[mid+1];
        for (int i = 1; i <= mid; i++) {
            sum_v2[i] = sum_v2[i-1] + 1L * b[i] * b[i];
            sum_v[i] =sum_v[i-1] + b[i];
        }
        for (int i = k; i <= mid; i++) {
            // v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];
            // v += b[i] - b[i - k];
            long v2 = sum_v2[i] - sum_v2[i-k];
            long v = sum_v[i] - sum_v[i-k];
            double avg = 1.0 * v / k;
            if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
                return true;
        }
        return false;
    }

第三步二分范围确定

那么这里的高度的最小值是1,最大值就是数组中元素的个数,也就是n。注意本题没有说一定能找到符合条件的高度,所以最后输出的时候要判断一下。

题目代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, k, T;
    static int[] a, b;

    static boolean check(int mid) {
        for (int i = 1; i <= mid; i++)
            b[i] = a[i];
        Arrays.sort(b, 1, mid + 1);
        long[] sum_v2 = new long[mid+1], sum_v = new long[mid+1];
        for (int i = 1; i <= mid; i++) {
            sum_v2[i] = sum_v2[i-1] + 1L * b[i] * b[i];
            sum_v[i] =sum_v[i-1] + b[i];
        }
        for (int i = k; i <= mid; i++) {
            // v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];
            // v += b[i] - b[i - k];
            long v2 = sum_v2[i] - sum_v2[i-k];
            long v = sum_v[i] - sum_v[i-k];
            double avg = 1.0 * v / k;
            if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        T = scanner.nextInt();
        a = new int[n + 1];
        b = new int[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = scanner.nextInt();
        int l = k, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if(check(l))System.out.println(l);
        else System.out.println(-1);
    }
}

http://www.kler.cn/a/586752.html

相关文章:

  • 神经网络:定义与核心原理
  • 基于 Verilog 的多路复用显示驱动设计与测试:实践与探索
  • Visual Studio里的调试(debugging)功能介绍
  • Tomato靶机
  • Vue 中的 v-for 如何遍历对象?
  • 【模拟算法】
  • misc19~21
  • 如何在AVL树中高效插入并保持平衡:一步步掌握旋转与平衡因子 —— 旋转篇
  • ​​​​​​​大语言模型安全风险分析及相关解决方案
  • P3379 【模板】最近公共祖先(LCA)【题解】(倍增法)
  • 链表·简单归并
  • OpenBMC:BmcWeb添加路由3 设置权限
  • 机器学习 Day05 pandas库
  • Linux 系统蓝牙音频服务实现分析
  • 基于深度学习的蛀牙智能检测与语音提示系统【python源码+Pyqt5界面+数据集+训练代码】
  • C语言数据类型取值范围及格式化符号
  • CentOS 8 停止维护后通过 rpm 包手动安装 docker
  • 《P1540 [NOIP 2010 提高组] 机器翻译 题解》
  • Scala语言的数据库编程
  • 基于雪雁算法(Snow Geese Algorithm,SGA)的多个无人机协同路径规划(可以自定义无人机数量及起始点),MATLAB代码