求vector里数的平均值

下面是 C++ 代码实现： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> scores = {90, 101, -5, 80, 120, 95, 110, 70}; // 过滤掉不合法的分数 scores.erase(remove_if(scores.begin(), scores.end(), [](int score) { return score < 1 || score > 100; }), scores.end()); if (scores.empty()) { // 所有的分数都不合法 cout << "0" << endl; } else { // 计算平均分数 int total_score = accumulate(scores.begin(), scores.end(), 0); double avg_score = static_cast<double>(total_score) / scores.size(); cout << avg_score << endl; } return 0; } ``` 输出结果为 86.25。

<think>嗯，用户想用C++实现一个算法，计算满足平均值大于等于某个给定常数的子数组的数量。这个问题看起来有点挑战性，我得先理清楚思路。 首先，我得明确问题。子数组是连续的，所以需要遍历所有可能的连续子数组，然后计算它们的平均值是否满足条件。但直接暴力枚举的话，时间复杂度会很高，比如O(n²)，当数组很大时可能不适用。 那有没有更高效的方法呢？比如数学上的转换。假设给定常数是k，那么平均值≥k相当于子数组的总和≥k乘以子数组长度。也就是sum >= k * length。将每个元素减去k，转化为新的数组，问题就变成找子数组的和≥0的数量。这样转换之后，问题变成了寻找和为非负数的子数组数目，这可能更方便处理。 接下来，我需要想如何高效计算这些子数组的数量。前缀和是一个常用的方法，但如何应用在这里呢？比如，假设我们有一个转换后的数组b，其中每个元素是原数组元素减去k。那么子数组的和就是前缀和数组的差。比如，前缀和数组s，子数组b[i...j]的和是s[j] - s[i-1]。我们需要s[j] - s[i-1] >= 0，即s[j] >= s[i-1]。所以问题转化为，对于每个j，找出前面有多少个i满足s[j] >= s[i-1]。 这时候，可以用归并排序中的分治思想来处理。在归并的过程中，统计右边的前缀和大于等于左边的个数。这类似于求逆序对的问题，但这里需要的是正序对的数量。因为每次合并左右两部分时，左边的已经排好序，右边的也排好序，所以对于右边的每个元素，可以找到左边有多少个元素小于等于它，这样就可以累加到总数中。这种方法的时间复杂度是O(n log n)，比暴力法好很多。 不过，在实现的时候需要注意前缀和数组的起始点。比如，前缀和数组通常是从0开始计算的，所以s[0] = 0，s[1] = b[0]，s[2] = b[0]+b[1]，依此类推。所以在分治的时候，需要考虑s数组的索引范围，以及如何分割左右两部分。比如，在归并排序的过程中，处理左半部分和右半部分的s值，然后统计满足条件的数目。 另外，还需要处理归并排序中的合并步骤，确保在合并左右两个有序数组时，能够正确统计数目。例如，当处理到右半部分的某个元素s[j]时，需要找出左半部分中有多少个元素s[i] <= s[j]，这可以通过双指针或者二分查找来实现。 最后，要注意边界条件和正确性测试。比如，当数组全为正数或全为负数时，算法是否能正确处理，以及一些简单的手动测试用例，比如示例中的情况是否能得到正确结果。 可能还有其他的优化方法，比如使用树状数组或者平衡二叉搜索树来维护前缀和，但分治方法可能在实现上更直观，且时间复杂度也足够好。 总结下来，步骤应该是： 1. 将原数组转换为每个元素减去k后的新数组。 2. 计算新数组的前缀和数组s。 3. 使用分治法统计s数组中满足s[j] >= s[i]且j > i的情况数目。 4. 返回统计结果作为满足条件的子数组数量。 现在，我需要把这个思路转化为具体的C++代码，并确保正确性。例如，前缀和数组的构建，分治函数的递归实现，合并时的统计方法，以及归并排序中的合并操作是否正确维护有序性。同时，还要处理可能的整数溢出问题，比如使用long long类型来存储前缀和。</think>### C++实现计算满足平均分条件的子数组数量算法 要解决计算数组中平均值≥给定常数的子数组数量问题，可以通过数学转换和分治策略优化时间复杂度。以下是分步解析： #### 一、数学转换简化条件 设数组为$arr$，长度为$n$，给定常数为$k$。需满足： $$\frac{\sum_{i=l}^{r} arr[i]}{r-l+1} \geq k$$ 等价于： $$\sum_{i=l}^{r} arr[i] \geq k \cdot (r-l+1)$$ 将每个元素减去$k$得到新数组$b[i] = arr[i] - k$，问题转化为计算$b$数组中**和≥0的子数组数量**[^2]。 #### 二、前缀和与分治策略 1. **构建前缀和数组**： $$s[0] = 0, \quad s[i] = s[i-1] + b[i-1]$$ 此时，子数组$b[l..r]$的和为$s[r+1] - s[l]$，需满足$s[r+1] \geq s[l]$。 2. **分治统计有效对数**： 利用归并排序思想，在合并左右有序前缀和数组时统计满足$s[j] \geq s[i]$的对数（其中$i < j$）。 #### 三、代码实现 ```cpp #include <vector> using namespace std; int merge_count(vector<long long>& s, int left, int right) { if (left >= right) return 0; int mid = (left + right) / 2; int count = merge_count(s, left, mid) + merge_count(s, mid + 1, right); // 统计跨越左右的满足条件的对数 int i = left, j = mid + 1; while (i <= mid && j <= right) { if (s[i] <= s[j]) { count += right - j + 1; i++; } else { j++; } } // 归并排序合并过程 vector<long long> temp; i = left, j = mid + 1; while (i <= mid && j <= right) { if (s[i] <= s[j]) temp.push_back(s[i++]); else temp.push_back(s[j++]); } while (i <= mid) temp.push_back(s[i++]); while (j <= right) temp.push_back(s[j++]); for (int k = 0; k < temp.size(); k++) s[left + k] = temp[k]; return count; } int count_subarrays(vector<int>& arr, double k) { int n = arr.size(); vector<long long> s(n + 1, 0); for (int i = 0; i < n; i++) { s[i + 1] = s[i] + arr[i] - k; // 转换为新数组的前缀和 } return merge_count(s, 0, n); } ``` #### 四、复杂度分析 - **时间复杂度**：$O(n \log n)$，归并分治策略保证效率。 - **空间复杂度**：$O(n)$，存储前缀和及临时数组[^3]。 #### 五、示例测试 输入： ```cpp vector<int> arr = {2, 1, 3}; double k = 2; ``` 输出应为3，即满足条件的子数组：`[2], [3], [2,1,3]`。