题解 | #统计量列表#

题目链接

统计量列表

题目描述

给定一个整数序列与一个窗口大小列表。程序需要处理多行输入，对每一行输入，执行以下操作：

滑动窗口处理：
- 确定最大窗口 $w_{max}$ 。如果输入序列长度小于 $w_{max}$ ，则该行输入无效，输出 []。
- 否则，需要生成 $N - w_{max} + 1$ 行结果，其中 $N$ 是序列长度。
- 第 $i$ 行结果（ $i$ 从 0 开始）对应一个公共的右边界 $R = i + w_{max} - 1$ 。
统计量计算：
- 对于第 $i$ 行的右边界 $R$ ，遍历窗口大小列表中的每一个窗口 $w$ 。
- 取一个“右对齐”的子数组，即 arr[R-w+1 ... R]。
- 对该子数组计算 5 个统计量（顺序固定）：mean（均值）、std（样本标准差）、min（最小值）、max（最大值）、slope（最小二乘法斜率）。
计算规则：
- std：样本标准差（自由度 ddof=1）。当窗口长度 $w=1$ 时，std=0。
- slope：最小二乘法直线斜率，横坐标为 $x = 0, 1, ..., w-1$ 。当 $w=1$ 时，slope=0。
输出格式：
- 将每一行、每个窗口计算出的 5 个统计量，按窗口列表的顺序依次拼接成一个大的列表。
- 数值格式化：整数不带小数点；非整数最多保留 3 位小数，四舍五入，并去掉末尾无意义的 0（例如 1.200 -> 1.2）。

解题思路

本题的核心是精确地模拟题目描述的整个流程，包括输入解析、滑动窗口的定位、五种统计量的计算以及复杂的数值格式化。

1. 输入解析

每行输入包含两个列表，形如 [1, 2, 3], [4, 5]。需要先将这一行字符串分割成两个列表字符串，再分别解析成整数列表。Python 的 ast.literal_eval 是处理这种格式的绝佳工具。

2. 主循环

对每组解析出的整数序列 arr 和窗口列表 windows，首先检查有效性：len(arr) < max(windows)。若无效则直接输出 []。
若有效，则进入主循环，遍历所有可能的右边界 R。循环次数为 len(arr) - max(windows) + 1。

3. 统计量计算

对于每个右边界 R 和每个窗口大小 w，我们得到子数组 sub_arr。

Mean (均值 $\bar{y}$ )： $\bar{y} = \frac{\sum_{i=0}^{w-1} y_i}{w}$
Std (样本标准差 $s$ )：当 $w>1$ 时， $s = \sqrt{\frac{\sum_{i=0}^{w-1} (y_i - \bar{y})^2}{w-1}}$ 。当 $w=1$ 时， $s=0$ 。
Min / Max：直接调用内置函数即可。
Slope (斜率 $m$ )：最小二乘法拟合直线 $y = mx+c$ 的斜率公式为： $m = \frac{w \sum (x_i y_i) - (\sum x_i)(\sum y_i)}{w \sum x_i^2 - (\sum x_i)^2}$ 其中 $y_i$ 是子数组的元素，对应的 $x_i$ 是 $0, 1, ..., w-1$ 。
- 公差为 1 的等差数列求和公式可以简化计算：
  - $\sum x_i = \frac{w(w-1)}{2}$
  - $\sum x_i^2 = \frac{(w-1)w(2w-1)}{6}$
- 分母 $D = w \sum x_i^2 - (\sum x_i)^2 = \frac{w^2(w^2-1)}{12}$ 。该分母仅在 $w=1$ 时为 0，符合题目 w=1 时斜率为 0 的要求。

4. 数值格式化

这是本题的一个难点。一个数值 v 需要按规则转换成字符串：

先将数值四舍五入到小数点后 3 位。
判断舍入后的值是否为整数。如果是，直接转换为不带小数点的整数字符串。
如果不是，则将其格式化为带 3 位小数的字符串，然后移除末尾多余的 0。例如，1.230 变为 1.23。

将所有计算出的统计量格式化后，按顺序拼接成最终的输出行。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

// 解析形如 "[1,2,3]" 的字符串
vector<long long> parse_array(const string& s) {
    vector<long long> res;
    long long num;
    char ch;
    stringstream ss(s);
    ss >> ch; // 读取 '['
    while (ss >> num) {
        res.push_back(num);
        ss >> ch; // 读取 ',' 或 ']'
    }
    return res;
}

// 格式化数字
string format_double(double val) {
    double rounded_val = round(val * 1000.0) / 1000.0;
    if (rounded_val == floor(rounded_val)) {
        return to_string((long long)rounded_val);
    }
    stringstream ss;
    ss << fixed << setprecision(3) << rounded_val;
    string s = ss.str();
    s.erase(s.find_last_not_of('0') + 1, string::npos);
    if (s.back() == '.') {
        s.pop_back();
    }
    return s;
}

void calculate_and_print(const vector<long long>& arr, const vector<long long>& windows) {
    long long max_w = 0;
    if (windows.empty()) {
        cout << "[]" << endl;
        return;
    }
    for (long long w : windows) {
        max_w = max(max_w, w);
    }

    if (arr.size() < max_w) {
        cout << "[]" << endl;
        return;
    }

    int n_rows = arr.size() - max_w + 1;
    for (int i = 0; i < n_rows; ++i) {
        int R = i + max_w - 1;
        vector<string> results;

        for (long long w : windows) {
            vector<double> sub_arr;
            for (int j = 0; j < w; ++j) {
                sub_arr.push_back(arr[R - w + 1 + j]);
            }

            // 均值
            double sum = accumulate(sub_arr.begin(), sub_arr.end(), 0.0);
            double mean = sum / w;

            // 样本标准差
            double std_dev = 0;
            if (w > 1) {
                double sq_sum = 0;
                for (double val : sub_arr) {
                    sq_sum += (val - mean) * (val - mean);
                }
                std_dev = sqrt(sq_sum / (w - 1));
            }

            // 最小值和最大值
            double min_val = *min_element(sub_arr.begin(), sub_arr.end());
            double max_val = *max_element(sub_arr.begin(), sub_arr.end());
            
            // 斜率
            double slope = 0;
            if (w > 1) {
                double sum_x = (double)w * (w - 1) / 2.0;
                double sum_y = sum;
                double sum_xy = 0;
                for(int j=0; j<w; ++j) {
                    sum_xy += j * sub_arr[j];
                }
                double sum_x_sq = (double)(w - 1) * w * (2 * w - 1) / 6.0;
                double num = w * sum_xy - sum_x * sum_y;
                double den = w * sum_x_sq - sum_x * sum_x;
                if (abs(den) > 1e-9) {
                    slope = num / den;
                }
            }

            results.push_back(format_double(mean));
            results.push_back(format_double(std_dev));
            results.push_back(format_double(min_val));
            results.push_back(format_double(max_val));
            results.push_back(format_double(slope));
        }

        cout << "[";
        for (size_t j = 0; j < results.size(); ++j) {
            cout << results[j] << (j == results.size() - 1 ? "" : ", ");
        }
        cout << "]" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    while (getline(cin, line)) {
        size_t pos = line.find("], [");
        if (pos == string::npos) {
            cout << "[]" << endl;
            continue;
        }
        string arr_str = line.substr(0, pos + 1);
        string win_str = line.substr(pos + 3);

        vector<long long> arr = parse_array(arr_str);
        vector<long long> windows = parse_array(win_str);
        calculate_and_print(arr, windows);
    }

    return 0;
}

import java.util.*;
import java.text.DecimalFormat;

public class Main {
    // 格式化数字
    private static String formatDouble(double val) {
        double roundedVal = Math.round(val * 1000.0) / 1000.0;
        if (roundedVal == (long) roundedVal) {
            return String.valueOf((long) roundedVal);
        }
        // 使用 DecimalFormat 自动处理尾随零
        DecimalFormat df = new DecimalFormat("#.###");
        return df.format(roundedVal);
    }

    private static void calculateAndPrint(List<Integer> arr, List<Integer> windows) {
        if (windows.isEmpty()) {
            System.out.println("[]");
            return;
        }
        int maxW = 0;
        for (int w : windows) {
            maxW = Math.max(maxW, w);
        }

        if (arr.size() < maxW) {
            System.out.println("[]");
            return;
        }

        int nRows = arr.size() - maxW + 1;
        for (int i = 0; i < nRows; ++i) {
            int R = i + maxW - 1;
            List<String> results = new ArrayList<>();

            for (int w : windows) {
                List<Double> subArr = new ArrayList<>();
                for (int j = 0; j < w; ++j) {
                    subArr.add((double) arr.get(R - w + 1 + j));
                }

                // 均值
                double sum = 0;
                for (double val : subArr) sum += val;
                double mean = sum / w;

                // 样本标准差
                double stdDev = 0;
                if (w > 1) {
                    double sqSum = 0;
                    for (double val : subArr) {
                        sqSum += Math.pow(val - mean, 2);
                    }
                    stdDev = Math.sqrt(sqSum / (w - 1));
                }

                // 最小值和最大值
                double minVal = Collections.min(subArr);
                double maxVal = Collections.max(subArr);

                // 斜率
                double slope = 0;
                if (w > 1) {
                    double sumX = (double) w * (w - 1) / 2.0;
                    double sumY = sum;
                    double sumXy = 0;
                    for (int j = 0; j < w; ++j) {
                        sumXy += j * subArr.get(j);
                    }
                    double sumXsq = (double) (w - 1) * w * (2 * w - 1) / 6.0;
                    double num = w * sumXy - sumX * sumY;
                    double den = w * sumXsq - sumX * sumX;
                    if (Math.abs(den) > 1e-9) {
                        slope = num / den;
                    }
                }

                results.add(formatDouble(mean));
                results.add(formatDouble(stdDev));
                results.add(formatDouble(minVal));
                results.add(formatDouble(maxVal));
                results.add(formatDouble(slope));
            }

            System.out.println("[" + String.join(", ", results) + "]");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String line = sc.nextLine();
            String[] parts = line.split("\\], \\[");
            if (parts.length != 2) {
                System.out.println("[]");
                continue;
            }
            
            try {
                String arrStr = parts[0].replaceAll("[\\[\\]]", "");
                String winStr = parts[1].replaceAll("[\\[\\]]", "");

                List<Integer> arr = new ArrayList<>();
                if (!arrStr.isEmpty()) {
                    for (String s : arrStr.split(",")) {
                        arr.add(Integer.parseInt(s.trim()));
                    }
                }

                List<Integer> windows = new ArrayList<>();
                if (!winStr.isEmpty()) {
                    for (String s : winStr.split(",")) {
                        windows.add(Integer.parseInt(s.trim()));
                    }
                }
                calculateAndPrint(arr, windows);
            } catch (Exception e) {
                System.out.println("[]");
            }
        }
    }
}

import math
import ast

def format_num(v):
    # 四舍五入到3位小数
    rounded_v = round(v * 1000) / 1000
    # 如果是整数，则返回整数字符串
    if rounded_v == int(rounded_v):
        return str(int(rounded_v))
    else:
        # 否则格式化为字符串，并移除末尾的0
        s = f"{rounded_v:.3f}"
        return s.rstrip('0')

def calculate_stats(sub_arr):
    w = len(sub_arr)
    
    # 均值
    mean = sum(sub_arr) / w
    
    # 样本标准差
    if w > 1:
        sq_sum = sum((x - mean) ** 2 for x in sub_arr)
        std = math.sqrt(sq_sum / (w - 1))
    else:
        std = 0
        
    # 最小值和最大值
    min_val = min(sub_arr)
    max_val = max(sub_arr)
    
    # 斜率
    if w > 1:
        sum_x = w * (w - 1) / 2
        sum_y = sum(sub_arr)
        sum_xy = sum(i * y for i, y in enumerate(sub_arr))
        sum_x_sq = (w - 1) * w * (2 * w - 1) / 6
        
        numerator = w * sum_xy - sum_x * sum_y
        denominator = w * sum_x_sq - sum_x ** 2
        slope = numerator / denominator if denominator != 0 else 0
    else:
        slope = 0
        
    return [mean, std, min_val, max_val, slope]

def main():
    while True:
        try:
            line = input()
            try:
                # 使用 ast.literal_eval 安全地解析列表
                arr, windows = ast.literal_eval(line)
            except (ValueError, SyntaxError):
                print("[]")
                continue

            if not windows:
                print("[]")
                continue
                
            max_w = max(windows)
            if len(arr) < max_w:
                print("[]")
                continue

            n_rows = len(arr) - max_w + 1
            for i in range(n_rows):
                R = i + max_w - 1
                row_results = []
                for w in windows:
                    sub_arr = arr[R - w + 1 : R + 1]
                    stats = calculate_stats(sub_arr)
                    row_results.extend(map(format_num, stats))
                
                print(f"[{', '.join(row_results)}]")

        except EOFError:
            break

if __name__ == "__main__":
    main()

算法及复杂度

算法：模拟、数学计算。该解法严格遵循题目描述的步骤，对每个滑动窗口位置和给定的窗口大小，进行直接的统计计算。
时间复杂度： $O(L \cdot N \cdot M \cdot W_{max})$ ，其中 $L$ 是输入数据的总行数， $N$ 是每行整数序列的平均长度， $M$ 是窗口列表的平均长度， $W_{max}$ 是最大窗口尺寸。对于每一行输入，有 $O(N)$ 个右边界，每个右边界要遍历 $M$ 个窗口，每个窗口的计算耗时与其长度成正比，最多为 $O(W_{max})$ 。
空间复杂度： $O(N + M)$ ，主要用于存储单行输入中的整数序列和窗口列表。