三项评分线性定价

题意

已知 $K$ 部手机，每部手机有三项评分 $(x_1, x_2, x_3)$ 和对应的价格 $y$ 。价格与评分之间满足线性关系：

$ $y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \beta_3 x_3$ $

根据这 $K$ 组已知数据拟合出四个系数 $\beta_0, \beta_1, \beta_2, \beta_3$ ，然后对 $N$ 部新手机预测价格，四舍五入到整数后输出。

思路

这是一道经典的多元线性回归问题，使用最小二乘法求解。

构造设计矩阵 $X$ （每行为 $[1, x_1, x_2, x_3]$ ）和价格向量 $Y$ ，参数向量 $\boldsymbol{\beta}$ 由正规方程给出：

$ $\boldsymbol{\beta} = (X^T X)^{-1} X^T Y$ $

实际实现中直接调用 numpy.linalg.lstsq 即可，它内部使用 SVD 分解求解，数值稳定性优于直接求逆。

拟合出 $\boldsymbol{\beta}$ 后，对每部待预测手机计算 $\hat{y} = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \beta_3 x_3$ ，四舍五入输出。

代码

import sys
import numpy as np

def main():
    data = sys.stdin.read().split()
    idx = 0
    K = int(data[idx]); idx += 1
    X = []
    Y = []
    for _ in range(K):
        x1 = int(data[idx]); idx += 1
        x2 = int(data[idx]); idx += 1
        x3 = int(data[idx]); idx += 1
        price = int(data[idx]); idx += 1
        X.append([1, x1, x2, x3])
        Y.append(price)
    X = np.array(X, dtype=np.float64)
    Y = np.array(Y, dtype=np.float64)
    # 正规方程求解: beta = (X^T X)^{-1} X^T Y
    beta = np.linalg.lstsq(X, Y, rcond=None)[0]
    N = int(data[idx]); idx += 1
    results = []
    for _ in range(N):
        x1 = int(data[idx]); idx += 1
        x2 = int(data[idx]); idx += 1
        x3 = int(data[idx]); idx += 1
        pred = beta[0] + beta[1] * x1 + beta[2] * x2 + beta[3] * x3
        results.append(str(round(pred)))
    print(' '.join(results))

main()

复杂度

时间复杂度： $O(K \cdot d^2 + d^3 + N \cdot d)$ ，其中 $d = 4$ 为特征维度。构造 $X^T X$ 需 $O(Kd^2)$ ，求解需 $O(d^3)$ ，预测需 $O(Nd)$ 。由于 $d$ 为常数，实际为 $O(K + N)$ 。
空间复杂度： $O(K \cdot d + N)$ ，存储设计矩阵和结果。