解题思路

本题是一个多元线性回归建模问题：已知 $K$ 部手机的三项评分特征与售价，要求拟合出线性关系，并用该关系预测新手机的价格。

1. 线性模型建立

设第 $i$ 个样本的三维特征为 $x^{(i)}=(x^{(i)}_1,x^{(i)}_2,x^{(i)}_3)$，对应售价为 $y^{(i)}$。 假设售价与特征满足线性关系：

$y^{(i)} = w_0 + w_1 x^{(i)}_1 + w_2 x^{(i)}_2 + w_3 x^{(i)}_3$

其中 $w_0$ 是偏置项，$w_1,w_2,w_3$ 是三个特征的权重。

为方便统一表示，把偏置并入特征，定义扩展特征：

$\tilde{x}^{(i)} = (1, x^{(i)}_1, x^{(i)}_2, x^{(i)}_3)$，参数向量为 $W=(w_0,w_1,w_2,w_3)$，则：

$y^{(i)} = W \cdot \tilde{x}^{(i)}$

2. 最小二乘目标

由于样本通常不能被一条直线（超平面）完全拟合，我们用最小二乘法，让预测值与真实值的平方误差之和最小：

$\min\limits_W \sum_{i=1}^{K}\left(W\cdot \tilde{x}^{(i)} - y^{(i)}\right)^2$

3. 求解方法（高斯消元/正规方程）

对上式求极值可得到一组线性方程（正规方程的结果），题目保证可解且数值稳定时，可以直接通过解线性方程组得到 $W$。工程实现上，不必显式写出复杂矩阵形式，只需构造一个 $4\times 4$ 的系数矩阵和长度为 $4$ 的常数向量，然后使用 高斯消元（Gauss Elimination） 求解：

• 扫描所有样本，累加得到系数矩阵中的各项（相当于统计不同特征乘积的和）
• 用高斯消元解出 $w_0,w_1,w_2,w_3$
• 对每个待预测手机特征代入 $y = w_0+w_1x_1+w_2x_2+w_3x_3$ 输出结果

复杂度分析

设：

• 已知手机数量为 (K)
• 特征维度为常数 4（含偏置）

时间复杂度

• 构造矩阵与计算 (X^T X)：(O(K))
• 矩阵求逆（4×4）：(O(1))
• 预测 (N) 台手机：(O(N))

总时间复杂度：(O(K + N))

空间复杂度

• 存储矩阵 (X, Y) 以及中间矩阵，规模固定

空间复杂度：(O(1))

代码实现

Python

import sys
import math

def linear_regression_predict(K, train_data, N, test_data):
    # X 是 K×4 矩阵，Y 是 K×1 向量
    X = []
    Y = []
    idx = 0
    for _ in range(K):
        x1, x2, x3, y = train_data[idx:idx+4]
        idx += 4
        X.append([1.0, x1, x2, x3])
        Y.append(y)

    # 计算 X^T * X 和 X^T * Y
    XT_X = [[0.0]*4 for _ in range(4)]
    XT_Y = [0.0]*4
    for i in range(K):
        for a in range(4):
            XT_Y[a] += X[i][a] * Y[i]
            for b in range(4):
                XT_X[a][b] += X[i][a] * X[i][b]

    # 高斯消元法求解 (X^T X)W = X^T Y
    # 构造增广矩阵
    A = [XT_X[i] + [XT_Y[i]] for i in range(4)]

    # 消元
    for i in range(4):
        pivot = A[i][i]
        for j in range(i, 5):
            A[i][j] /= pivot
        for k in range(4):
            if k != i:
                factor = A[k][i]
                for j in range(i, 5):
                    A[k][j] -= factor * A[i][j]

    W = [A[i][4] for i in range(4)]

    # 预测
    res = []
    idx = 0
    for _ in range(N):
        x1, x2, x3 = test_data[idx:idx+3]
        idx += 3
        y_pred = W[0] + W[1]*x1 + W[2]*x2 + W[3]*x3
        res.append(str(int(round(y_pred))))
    return res

def main():
    data = sys.stdin.read().strip().split()
    pos = 0
    K = int(data[pos]); pos += 1
    train_data = list(map(int, data[pos:pos+4*K]))
    pos += 4*K
    N = int(data[pos]); pos += 1
    test_data = list(map(int, data[pos:pos+3*N]))

    ans = linear_regression_predict(K, train_data, N, test_data)
    print(" ".join(ans))

if __name__ == "__main__":
    main()

Java

import java.util.Scanner;

public class Main {

    // 使用正规方程法进行线性回归预测
    static long[] predict(int K, int[] train, int N, int[] test) {
        double[][] XT_X = new double[4][4];
        double[] XT_Y = new double[4];

        // 构造 X^T X 和 X^T Y
        int idx = 0;
        for (int i = 0; i < K; i++) {
            double[] x = new double[]{1, train[idx], train[idx+1], train[idx+2]};
            double y = train[idx+3];
            idx += 4;

            for (int a = 0; a < 4; a++) {
                XT_Y[a] += x[a] * y;
                for (int b = 0; b < 4; b++) {
                    XT_X[a][b] += x[a] * x[b];
                }
            }
        }

        // 构造增广矩阵
        double[][] A = new double[4][5];
        for (int i = 0; i < 4; i++) {
            System.arraycopy(XT_X[i], 0, A[i], 0, 4);
            A[i][4] = XT_Y[i];
        }

        // 高斯消元
        for (int i = 0; i < 4; i++) {
            double pivot = A[i][i];
            for (int j = i; j < 5; j++) {
                A[i][j] /= pivot;
            }
            for (int k = 0; k < 4; k++) {
                if (k != i) {
                    double factor = A[k][i];
                    for (int j = i; j < 5; j++) {
                        A[k][j] -= factor * A[i][j];
                    }
                }
            }
        }

        double[] W = new double[4];
        for (int i = 0; i < 4; i++) {
            W[i] = A[i][4];
        }

        // 预测
        long[] res = new long[N];
        idx = 0;
        for (int i = 0; i < N; i++) {
            double x1 = test[idx++];
            double x2 = test[idx++];
            double x3 = test[idx++];
            double y = W[0] + W[1]*x1 + W[2]*x2 + W[3]*x3;
            res[i] = Math.round(y);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int[] train = new int[4*K];
        for (int i = 0; i < 4*K; i++) train[i] = sc.nextInt();
        int N = sc.nextInt();
        int[] test = new int[3*N];
        for (int i = 0; i < 3*N; i++) test[i] = sc.nextInt();

        long[] ans = predict(K, train, N, test);
        for (int i = 0; i < ans.length; i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(ans[i]);
        }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 使用正规方程法进行线性回归
vector<long long> predict(int K, vector<int>& train, int N, vector<int>& test) {
    double XT_X[4][4] = {0};
    double XT_Y[4] = {0};

    int idx = 0;
    for (int i = 0; i < K; i++) {
        double x[4] = {1.0, (double)train[idx], (double)train[idx+1], (double)train[idx+2]};
        double y = train[idx+3];
        idx += 4;

        for (int a = 0; a < 4; a++) {
            XT_Y[a] += x[a] * y;
            for (int b = 0; b < 4; b++) {
                XT_X[a][b] += x[a] * x[b];
            }
        }
    }

    // 增广矩阵
    double A[4][5];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) A[i][j] = XT_X[i][j];
        A[i][4] = XT_Y[i];
    }

    // 高斯消元
    for (int i = 0; i < 4; i++) {
        double pivot = A[i][i];
        for (int j = i; j < 5; j++) A[i][j] /= pivot;
        for (int k = 0; k < 4; k++) {
            if (k != i) {
                double factor = A[k][i];
                for (int j = i; j < 5; j++) {
                    A[k][j] -= factor * A[i][j];
                }
            }
        }
    }

    double W[4];
    for (int i = 0; i < 4; i++) W[i] = A[i][4];

    vector<long long> res(N);
    idx = 0;
    for (int i = 0; i < N; i++) {
        double x1 = test[idx++];
        double x2 = test[idx++];
        double x3 = test[idx++];
        double y = W[0] + W[1]*x1 + W[2]*x2 + W[3]*x3;
        res[i] = llround(y);
    }
    return res;
}

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

    int K;
    cin >> K;
    vector<int> train(4*K);
    for (int i = 0; i < 4*K; i++) cin >> train[i];

    int N;
    cin >> N;
    vector<int> test(3*N);
    for (int i = 0; i < 3*N; i++) cin >> test[i];

    vector<long long> ans = predict(K, train, N, test);
    for (int i = 0; i < ans.size(); i++) {
        if (i) cout << " ";
        cout << ans[i];
    }
    return 0;
}

题目内容

手机的售价跟手机的软硬件特性有关系。硬件规格越高、软件特性越丰富，则手机给消费者提供的价值越大，同时手机的售价越高。我们在市面上收集了若干款手机，从硬件能力、系统流畅度、$AI$能力$3$个方面对这些手机进行打分，并记录这些手机的分数和售价。请你使用最小二乘法建立线性回归模型，对这3个特征和手机售价的关系进行线性回归，然后预测若干款待上市的手机型号应该卖多少价钱。

该题目的数据保证最小二乘法有解析解。建议使用正规方程法，即矩阵求解。如果使用梯度下降法，请迭代至预测值的小数点后第一位稳定不变，以保证精度满足题目要求。

输入描述

第$1$行，正整数$K$，已知的手机个数。

第$2$行，$K$个手机的特征和售价记录，均为整数。用空格分割，一共$4K$数字是售个数字。每$4$个数字为一组，第$1$-$3$个数字为特征值,第4个数字是售价。。

第$3$行，正整数$N$，待估价的手机数量。

第$4$行，$N$个手机型号对应的特征，均为整数。用空格分割，一共$3N$个数字。每$3$个数字为一组，分别为$3$个特征值。

输出描述

$N$个正整数，代表每个手机的价格，使用空格分割，四舍五入取整数。

样例1

输入

10
86 99 20 3595 175 171 90 6596 194 42 47 4691 192 172 26 5927 44 20 168 4169 61 138 64 4348 161 42 85 4791 197 181 99 7126 170 55 95 5208 26 158 142 5231
2
159 135 173 120 144 59

输出

7116 5120 

说明

已知$10$台手机的评分和售价，以第$1$台手机型号为例，硬件能力评分为$86$、系统流畅度评分为$99$、AI能力评分为$20$，售价为$3595$。以此类推。

需要求解$2$台手机的预期售价，其中第$1$台手机的硬件能力评分为$159$、系统流畅度评分为$135$、AI能力评分为$173$，使用正规方程法求解，得到的预期售价求整结果是$7116$。以此类推。

样例2

输入

4
30 23 24 1999 55 53 46 2999 68 85 78 3999 113 90 103 4999
1
126 114 143

输出

6009

说明

已知$4$台手机的评分和售价，以第$1$台手机为例，硬件能力评分为$30$、系统流畅度评分为$23$、$AI$能力评分为$24$，售价为$1999$。以此类推。需要求解$1$台手机的预期售价，这台手机的硬件能力评分为$126$、系统流畅度评分为$114$、$AI$能力评分为$143$，使用正规方程法求解，得到的预期售价的求整结果是$6009$。