题解 | #牛牛的数学作业#

题目链接

牛牛的数学作业

题目描述

牛牛有多张数学试卷，每张试卷上有 k 个数字。对于每张试卷，她需要计算：

极差: 试卷上数字的最大值减去最小值。
方差: 所有数字与其平均值的差的平方的平均值，即 (1/k) * Σ( (x_i - μ)^2 )，其中 μ 是平均数。

输入描述:

第一行是一个整数 T，表示试卷数量。
接下来 T 组数据，每组数据占两行：
- 第一行是整数 k，表示数字个数。
- 第二行是 k 个整数。

输出描述:

对于每张试卷，输出一行，包含两个数：极差（整数）和方差（保留3位小数的浮点数），用空格隔开。

解题思路

本题需要处理多组测试数据，对每一组数据分别进行统计计算。计算方差需要先知道平均数，而计算平均数需要所有数字的总和。因此，一个清晰的解法是采用"两遍扫描"的策略。

对于每一张试卷（即每一个测试用例）：

第一次扫描 (First Pass):
- 读取该试卷的数字个数 k。
- 将 k 个数字读入一个数组或列表中，因为后续计算方差时需要再次用到它们。
- 在读取的同时，完成三件事：
  - 计算所有数字的总和 total_sum。
  - 找出最大值 max_val。
  - 找出最小值 min_val。
- 这一步结束后，我们就有了计算极差和平均数所需的所有信息。
计算极差和平均数:
- 极差 range = max_val - min_val。
- 平均数 mean = (double)total_sum / k。注意，这里必须进行浮点数除法，否则会丢失精度。
第二次扫描 (Second Pass):
- 现在我们有了平均数 mean。
- 再次遍历存储好的 k 个数字。对于每个数字 x_i，计算它与平均数的差的平方 (x_i - mean)^2，并将这个结果累加到一个新的变量 sum_of_squares 中。
- sum_of_squares = Σ (x_i - mean)^2
计算方差并输出:
- 方差 variance = sum_of_squares / k。
- 按照 "极差方差" 的格式输出结果，注意方差需要格式化为保留三位小数。

这种分步计算的方法逻辑清晰，易于实现，并且能有效处理问题。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>   // 用于求和 (accumulate)
#include <algorithm> // 用于查找最小/最大元素 (minmax_element)
#include <cmath>     // 用于幂运算 (pow)
#include <iomanip>   // 用于格式化输出 (fixed, setprecision)

using namespace std;

void solve() {
    int k;
    cin >> k;
    vector<int> nums(k);
    
    long long total_sum = 0;
    int max_val = -2e9, min_val = 2e9;

    for (int i = 0; i < k; ++i) {
        cin >> nums[i];
        total_sum += nums[i];
        if (nums[i] > max_val) max_val = nums[i];
        if (nums[i] < min_val) min_val = nums[i];
    }
    
    int range = max_val - min_val;
    double mean = double(total_sum) / k;
    
    double sum_of_squares = 0.0;
    for (int x : nums) {
        sum_of_squares += pow(x - mean, 2);
    }
    
    double variance = sum_of_squares / k;
    
    cout << range << " " << fixed << setprecision(3) << variance << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void solve(Scanner sc) {
        int k = sc.nextInt();
        int[] nums = new int[k];
        
        long totalSum = 0;
        int maxVal = Integer.MIN_VALUE;
        int minVal = Integer.MAX_VALUE;

        for (int i = 0; i < k; i++) {
            nums[i] = sc.nextInt();
            totalSum += nums[i];
            if (nums[i] > maxVal) maxVal = nums[i];
            if (nums[i] < minVal) minVal = nums[i];
        }

        int range = maxVal - minVal;
        double mean = (double) totalSum / k;

        double sumOfSquares = 0.0;
        for (int x : nums) {
            sumOfSquares += Math.pow(x - mean, 2);
        }

        double variance = sumOfSquares / k;

        System.out.printf("%d %.3f%n", range, variance);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            solve(sc);
        }
    }
}

import math

def solve():
    k = int(input())
    nums = list(map(int, input().split()))
    
    # 第一次扫描：获取总和、最小值和最大值
    total_sum = sum(nums)
    max_val = max(nums)
    min_val = min(nums)
    
    # 计算极差和平均值
    range_val = max_val - min_val
    mean = total_sum / k
    
    # 第二次扫描：获取离差平方和
    sum_of_squares = sum([(x - mean) ** 2 for x in nums])
    
    # 计算方差
    variance = sum_of_squares / k
    
    # 格式化输出
    print(f"{range_val} {variance:.3f}")

# 处理多组测试用例的主循环
T = int(input())
for _ in range(T):
    solve()

算法及复杂度

算法：两遍扫描法进行统计计算。
时间复杂度：对于每张含 k 个数字的试卷，我们需要遍历数据两次。因此处理单张试卷的复杂度是 $\mathcal{O}(k)$ 。如果有 T 张试卷，总时间复杂度为所有试卷复杂度之和。
空间复杂度：对于每张试卷，我们需要 $\mathcal{O}(k)$ 的空间来存储 k 个数字，以便进行第二次扫描。