题目 3217 ⭐成绩统计⭐【滑动窗口 + 二分搜索】蓝桥杯2024年第十五届省赛
小蓝的班上有 n n n 个人,一次考试之后小蓝想统计同学们的成绩,第 i 名同学的成绩为 a i a_i ai 。当小蓝统计完前 x x x 名同学的成绩后,他可以从 1 ∼ x 1 ∼ x 1∼x 中选出任意 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(vi−v′)/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 。
关键点
-
问题目标:找到最小的 x x x,使得在前 x x x 名同学的成绩中,存在一个大小为 k k k 的子集,其方差小于 T T T。
-
方差的含义:
- 方差越小,说明数据越集中。
- 如果选择的 k k k 个数非常接近,方差会很小。
-
解决思路:
- 对前 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 n⋅logn)
-
空间复杂度:
- 存储子集: O ( n ) O(n) O(n)
总结
- 通过排序和滑动窗口,可以高效地检查是否存在满足条件的子集。
- 二分搜索用于快速找到最小的 x x x。
- 该方法在时间和空间复杂度上都是可行的,适用于中等规模的数据。
相关文章:
题目 3217 ⭐成绩统计⭐【滑动窗口 + 二分搜索】蓝桥杯2024年第十五届省赛
小蓝的班上有 n n n 个人,一次考试之后小蓝想统计同学们的成绩,第 i 名同学的成绩为 a i a_i ai 。当小蓝统计完前 x x x 名同学的成绩后,他可以从 1 ∼ x 1 ∼ x 1∼x 中选出任意 k k k 名同学的成绩,计算出这 k k k 个成…...
URL中的特殊字符与web安全
在现代Web应用中,URL作为客户端与服务器之间的通信桥梁,承载着大量的重要信息。URL中的特殊字符,看似只是一些常见的符号,但在Web安全领域,它们与其他安全知识密切相关,如在Base64编码、SQL注入,…...
八卡5090服务器首发亮相!
AI 人工智能领域热度居高不下。OpenAI 的 GPT - 4 凭强悍语言处理能力,在内容创作、智能客服等领域广泛应用。清华大学团队的 DeepSeek 大模型在深度学习训练优势突出,正促使各行业应用端算力需求向推理主导转变,呈爆发式增长 。 随着 DeepS…...
esp32驱动带字库芯片TFT屏幕
前言 学习esp32单片机开发,前段时间在网上买了一块2.0寸TFT屏幕。 长这个样子,这个屏幕带汉字字库的硬件模块。我仔细看了一下这个字库模块上面写的字是25Q32FVSIG 1336 文档 卖家也发来了开发文档,是个doc文档,张这个样子。 开…...
为AI聊天工具添加一个知识系统 之138 设计重审 之2 文章学 引言之2 附加符号学附属诠释学附随工程学(联系)
本文要点 要点 符号学大局观: 诠释学(当代 加成[0]:“预期”和“预设” 两者的 不期而遇 。“邂逅”) 我们在文章学工具设计中 以全局观考虑:嵌入编程工具的逻辑性底( 哲学诠释 下确界) 并…...
java环境部署
java环境部署 一、准备工作 jrejdkeclipse jdk下载:21和1.8-----官网:Oracle:Java 下载 |神谕 该处选择要依据自身的系统类型选择下载 idea的下载安装:IntelliJ IDEA | Other Versions 二、安装 三、环境配置 四、使用 五、i…...
正点原子[第三期]Arm(iMX6U)Linux移植学习笔记-2.1 uboot简介
前言: 本文是根据哔哩哔哩网站上“Arm(iMX6U)Linux系统移植和根文件系统构键篇”视频的学习笔记,在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。 引用: …...
CentOS 7.9 安装 ClickHouse 文档
1. 环境准备 确保系统为 CentOS 7.9,并已安装 Docker。如果未安装 Docker,请先安装 Docker。 安装 Docker # 卸载旧版本 Docker(如果有) sudo yum remove -y docker docker-client docker-client-latest docker-common docker-…...
高考數學。。。
2024上 具体来说,直线的参数方程可以写为: x1t y−t z1t 二、简答题(本大题共5小题,每小题7分,共35分。) 12.数学学习评价不仅要关注结果评价,也要关注过程评价。简要说明过程评价应关注哪几个方面。…...
使用GitLink个人建站服务部署Allure在线测试报告
更多技术文章,访问软件测试社区 文章目录 🚀前言🔑开通GitLink个人建站服务1. 前提条件2. 登录GitLink平台(https://www.gitlink.org.cn/login)3. 进入设置>个人建站>我的站点4. 新建站点5. 去仓部进行部署6. 安…...
Linux 上离线安装 python3
在Linux系统上进行离线安装 Python3,通常是因为目标机器没有网络连接。以下是一个通用的步骤指南,帮助你在这种情况下成功安装Python 3: 下载安装包 选择一台有网络连接的机器:这台机器的操作系统应该尽可能与目标机器相同或相似…...
js操作字符串的常用方法
1. 查找和截取 1.1 indexOf 作用:查找子字符串在字符串中首次出现的位置。 是否改变原字符串:不会改变原字符串。 返回值:如果找到子字符串,返回其起始索引(从 0 开始);如果未…...
自动化学习-使用git进行版本管理
目录 一、为什么要学习git 二、git是什么 三、git如何使用 1、git的下载安装和配置 2、git常用的命令 3、gitee远程仓库的使用 (1)注册 (2)创建仓库 (3)配置公钥(建立电脑和git…...
GCC RISCV 后端 -- GCC Passes 注释
在前面文章提到,当GCC 前端完成对C源代码解析完成后,就会使用 处理过程(Passes)机制,通过一系列的处理过程,将 GENERIC IR 表示的C程序 转步转换成 目标机器的汇编语言。过程描述如下图所示: 此…...
Ollama存在安全风险的情况通报及解决方案
据清华大学网络空间测绘联合研究中心分析,开源跨平台大模型工具Ollama默认配置存在未授权访问与模型窃取等安全隐患。鉴于目前DeepSeek等大模型的研究部署和应用非常广泛,多数用户使用Ollama私有化部署且未修改默认配置,存在数据泄露、算力盗…...
IDEA Generate POJOs.groovy 踩坑小计 | 生成实体 |groovy报错
一、无法生成注释或生成的注释是null 问题可能的原因: 1.没有从表里提取注释信息,修改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 的前端项目中,执行上述指令,即初始化 Tailwind CSS 时,报如下错误 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 首个预览版已经在前两天发布,该版本在 .NET Runtime、SDK、libraries、C#、ASP.NET Core、Blazor 和 .NET MAUI 等多个方面都有重大改进和增强。其中C# 14 预览版也伴随着.NET 10预览版一起发布了,今天就和大家一起体验一下.NET 10 和 C# 14 。 …...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 ;/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
