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

题目 3217 ⭐成绩统计⭐【滑动窗口 + 二分搜索】蓝桥杯2024年第十五届省赛

小蓝的班上有 n n n 个人,一次考试之后小蓝想统计同学们的成绩,第 i 名同学的成绩为 a i a_i ai 。当小蓝统计完前 x x x 名同学的成绩后,他可以从 1 ∼ x 1 ∼ x 1x 中选出任意 k k k 名同学的成绩,计算出这 k k k 个成绩的方差。小蓝至少要检查多少个人的成绩,才有可能选出 k k k 名同学,他们的方差小于一个给定的值 T T T

提示: k k k 个数 v 1 , v 2 , ⋯ , v k v_1, v_2, \cdots, v_k v1,v2,,vk 的方差 σ 2 σ^2 σ2 定义为: σ 2 = ∑ k i = 1 ( v i − v ′ ) / k σ^2=∑ k_i=1(v_i−v')/k σ2=ki=1(viv)/k ,其中 v ′ v' v 表示 v v v 的平均值, v ′ = ∑ k i = 1 v i k v'=∑k_{i=1} \frac{v_i}{k} v=ki=1kvi

关键点

  1. 问题目标:找到最小的 x x x,使得在前 x x x 名同学的成绩中,存在一个大小为 k k k 的子集,其方差小于 T T T

  2. 方差的含义

    • 方差越小,说明数据越集中。
    • 如果选择的 k k k 个数非常接近,方差会很小。
  3. 解决思路

    • 对前 x x x 名同学的成绩排序。
    • 使用 滑动窗口 检查所有连续的 k k k 个数的方差是否小于 T T T
    • 通过 二分搜索 找到最小的 x x x
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;// 计算 k 个数的方差
double calculateVariance(const vector<int>& nums, int start, int k) {double sum = 0;for (int i = start; i < start + k; i++) {sum += nums[i];}double mean = sum / k; // 平均值double variance = 0;for (int i = start; i < start + k; i++) {variance += (nums[i] - mean) * (nums[i] - mean);}return variance / k;
}// 检查前 x 个数中是否存在 k 个数的方差小于 T
bool check(const vector<int>& a, int x, int k, double T) {vector<int> subset(a.begin(), a.begin() + x); // 取前 x 个数sort(subset.begin(), subset.end()); // 排序for (int i = 0; i <= x - k; i++) { // 滑动窗口double variance = calculateVariance(subset, i, k);if (variance < T) {return true;}}return false;
}// 二分搜索找到最小的 x
int findMinX(const vector<int>& a, int k, double T) {int n = a.size();int left = k, right = n; // x 的最小值是 k,最大值是 nint result = n + 1; // 初始化为一个不可能的值while (left <= right) {int mid = left + (right - left) / 2;if (check(a, mid, k, T)) {result = mid; // 更新结果right = mid - 1; // 尝试更小的 x} else {left = mid + 1; // 尝试更大的 x}}return result <= n ? result : -1; // 如果找到返回 x,否则返回 -1
}

复杂度分析

  • 时间复杂度:

    • 排序: O ( x l o g x ) O(x\ log\ x) O(x log x),其中 x x x 是检查的人数
    • 滑动窗口检查方差: O ( x ) O(x) O(x)
    • 二分搜索: O ( l o g n ) O(log\ n) O(log n)
    • 总复杂度 O ( n l o g n ⋅ l o g n ) O(nlog\ n⋅logn) O(nlog nlogn)
  • 空间复杂度:

    • 存储子集: O ( n ) O(n) O(n)

总结

  • 通过排序和滑动窗口,可以高效地检查是否存在满足条件的子集。
  • 二分搜索用于快速找到最小的 x x x
  • 该方法在时间和空间复杂度上都是可行的,适用于中等规模的数据。

相关文章:

题目 3217 ⭐成绩统计⭐【滑动窗口 + 二分搜索】蓝桥杯2024年第十五届省赛

小蓝的班上有 n n n 个人&#xff0c;一次考试之后小蓝想统计同学们的成绩&#xff0c;第 i 名同学的成绩为 a i a_i ai​ 。当小蓝统计完前 x x x 名同学的成绩后&#xff0c;他可以从 1 ∼ x 1 ∼ x 1∼x 中选出任意 k k k 名同学的成绩&#xff0c;计算出这 k k k 个成…...

URL中的特殊字符与web安全

在现代Web应用中&#xff0c;URL作为客户端与服务器之间的通信桥梁&#xff0c;承载着大量的重要信息。URL中的特殊字符&#xff0c;看似只是一些常见的符号&#xff0c;但在Web安全领域&#xff0c;它们与其他安全知识密切相关&#xff0c;如在Base64编码、SQL注入&#xff0c…...

八卡5090服务器首发亮相!

AI 人工智能领域热度居高不下。OpenAI 的 GPT - 4 凭强悍语言处理能力&#xff0c;在内容创作、智能客服等领域广泛应用。清华大学团队的 DeepSeek 大模型在深度学习训练优势突出&#xff0c;正促使各行业应用端算力需求向推理主导转变&#xff0c;呈爆发式增长 。 随着 DeepS…...

esp32驱动带字库芯片TFT屏幕

前言 学习esp32单片机开发&#xff0c;前段时间在网上买了一块2.0寸TFT屏幕。 长这个样子&#xff0c;这个屏幕带汉字字库的硬件模块。我仔细看了一下这个字库模块上面写的字是25Q32FVSIG 1336 文档 卖家也发来了开发文档&#xff0c;是个doc文档&#xff0c;张这个样子。 开…...

为AI聊天工具添加一个知识系统 之138 设计重审 之2 文章学 引言之2 附加符号学附属诠释学附随工程学(联系)

本文要点 要点 符号学大局观&#xff1a; 诠释学&#xff08;当代 加成[0]&#xff1a;“预期”和“预设” 两者的 不期而遇 。“邂逅”&#xff09; 我们在文章学工具设计中 以全局观考虑&#xff1a;嵌入编程工具的逻辑性底&#xff08; 哲学诠释 下确界&#xff09; 并…...

java环境部署

java环境部署 一、准备工作 jrejdkeclipse jdk下载&#xff1a;21和1.8-----官网&#xff1a;Oracle&#xff1a;Java 下载 |神谕 该处选择要依据自身的系统类型选择下载 idea的下载安装&#xff1a;IntelliJ IDEA | Other Versions 二、安装 三、环境配置 四、使用 五、i…...

正点原子[第三期]Arm(iMX6U)Linux移植学习笔记-2.1 uboot简介

前言&#xff1a; 本文是根据哔哩哔哩网站上“Arm(iMX6U)Linux系统移植和根文件系统构键篇”视频的学习笔记&#xff0c;在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。 引用&#xff1a; …...

CentOS 7.9 安装 ClickHouse 文档

1. 环境准备 确保系统为 CentOS 7.9&#xff0c;并已安装 Docker。如果未安装 Docker&#xff0c;请先安装 Docker。 安装 Docker # 卸载旧版本 Docker&#xff08;如果有&#xff09; sudo yum remove -y docker docker-client docker-client-latest docker-common docker-…...

高考數學。。。

2024上 具体来说&#xff0c;直线的参数方程可以写为&#xff1a; x1t y−t z1t 二、简答题(本大题共5小题&#xff0c;每小题7分&#xff0c;共35分。) 12.数学学习评价不仅要关注结果评价&#xff0c;也要关注过程评价。简要说明过程评价应关注哪几个方面。…...

使用GitLink个人建站服务部署Allure在线测试报告

更多技术文章&#xff0c;访问软件测试社区 文章目录 &#x1f680;前言&#x1f511;开通GitLink个人建站服务1. 前提条件2. 登录GitLink平台&#xff08;https://www.gitlink.org.cn/login&#xff09;3. 进入设置>个人建站>我的站点4. 新建站点5. 去仓部进行部署6. 安…...

Linux 上离线安装 python3

在Linux系统上进行离线安装 Python3&#xff0c;通常是因为目标机器没有网络连接。以下是一个通用的步骤指南&#xff0c;帮助你在这种情况下成功安装Python 3&#xff1a; 下载安装包 选择一台有网络连接的机器&#xff1a;这台机器的操作系统应该尽可能与目标机器相同或相似…...

js操作字符串的常用方法

1. 查找和截取​​​​​​​ 1.1 indexOf 作用&#xff1a;查找子字符串在字符串中首次出现的位置。 是否改变原字符串&#xff1a;不会改变原字符串。 返回值&#xff1a;如果找到子字符串&#xff0c;返回其起始索引&#xff08;从 0 开始&#xff09;&#xff1b;如果未…...

自动化学习-使用git进行版本管理

目录 一、为什么要学习git 二、git是什么 三、git如何使用 1、git的下载安装和配置 2、git常用的命令 3、gitee远程仓库的使用 &#xff08;1&#xff09;注册 &#xff08;2&#xff09;创建仓库 &#xff08;3&#xff09;配置公钥&#xff08;建立电脑和git…...

GCC RISCV 后端 -- GCC Passes 注释

在前面文章提到&#xff0c;当GCC 前端完成对C源代码解析完成后&#xff0c;就会使用 处理过程&#xff08;Passes&#xff09;机制&#xff0c;通过一系列的处理过程&#xff0c;将 GENERIC IR 表示的C程序 转步转换成 目标机器的汇编语言。过程描述如下图所示&#xff1a; 此…...

Ollama存在安全风险的情况通报及解决方案

据清华大学网络空间测绘联合研究中心分析&#xff0c;开源跨平台大模型工具Ollama默认配置存在未授权访问与模型窃取等安全隐患。鉴于目前DeepSeek等大模型的研究部署和应用非常广泛&#xff0c;多数用户使用Ollama私有化部署且未修改默认配置&#xff0c;存在数据泄露、算力盗…...

IDEA Generate POJOs.groovy 踩坑小计 | 生成实体 |groovy报错

一、无法生成注释或生成的注释是null 问题可能的原因&#xff1a; 1.没有从表里提取注释信息&#xff0c;修改def calcFields(table)方法即可 def calcFields(table) {DasUtil.getColumns(table).reduce([]) { fields, col ->def spec Case.LOWER.apply(col.getDataType().…...

阿里云云监控资源告警常用模板

阿里云云监控资源告警常用模板 {"HostAvailabilityTemplate": [],"Description": "","SystemEventTemplates": [],"AlertTemplatesJson": {"kvstore_standard": [{"displayName": "Connection usa…...

Tailwind CSS 问题:npm error could not determine executable to run

问题与处理策略 问题描述 npx tailwindcss init -p在使用 Tailwind CSS 的前端项目中&#xff0c;执行上述指令&#xff0c;即初始化 Tailwind CSS 时&#xff0c;报如下错误 npm error could not determine executable to run# 报错npm 错误无法确定要运行的可执行文件问题…...

vue基本功

watchEffect和watch watchEffect默认 immdiate 是 true,而且自动收集依赖 watch需要手动写依赖,immdiate 默认是 false toRef和toRefs toRef: 复制 reactive 里的单个属性并转成 ref toRefs: 复制 reactive 里的所有属性并转成 ref vue3中使用vuex import { useStore } f…...

.NET10 - 预览版1新功能体验(一)

.NET 10 首个预览版已经在前两天发布&#xff0c;该版本在 .NET Runtime、SDK、libraries、C#、ASP.NET Core、Blazor 和 .NET MAUI 等多个方面都有重大改进和增强。其中C# 14 预览版也伴随着.NET 10预览版一起发布了&#xff0c;今天就和大家一起体验一下.NET 10 和 C# 14 。 …...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...