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

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

提示：$k$ 个数 $v_1,v_2,\cdots ,v_k$ 的方差 ${\sigma }^2$ 定义为：${\sigma }^2=\sum k_i=1(v_i-v^{\prime })/k$ ，其中 $v^{\prime }$ 表示 $v$ 的平均值，$v^{\prime }=\sum k_{i=1}\frac{v_i}{k}$ 。

关键点

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

2. 方差的含义：

   • 方差越小，说明数据越集中。
   • 如果选择的 $k$ 个数非常接近，方差会很小。

3. 解决思路：

   • 对前 $x$ 名同学的成绩排序。
   • 使用 滑动窗口 检查所有连续的 $k$ 个数的方差是否小于 $T$。
   • 通过 二分搜索 找到最小的 $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(xlogx)$，其中 $x$ 是检查的人数
  • 滑动窗口检查方差：$O(x)$
  • 二分搜索：$O(logn)$
  • 总复杂度：$O(nlogn\cdot logn)$

• 空间复杂度：

  • 存储子集：$O(n)$

总结

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