欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 游戏 > 题目 3217 ⭐成绩统计⭐【滑动窗口 + 二分搜索】蓝桥杯2024年第十五届省赛

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

2025/7/11 10:11:00 来源:https://blog.csdn.net/Vitalia/article/details/146030816  浏览:    关键词:题目 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
  • 该方法在时间和空间复杂度上都是可行的,适用于中等规模的数据。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词