题目理解

我们有 $m$ 个学生，$n$ 门课程，每个学生可能选部分课程。
目标：为每门课 $i$ 找到一个修正值 $d_i$，使得：

调整后第 $i$ 门课的平均分 = 选第 $i$ 门课的所有学生的所有课程平均分

---

核心数学模型

1. 建立方程

设第 $i$ 门课的修正值为 $d_i$，第 $j$ 个学生的平均分为 $s_j$。

对于第 $i$ 门课，调整后该课的平均分为：

$$\frac{\sum_{j \in S_i} (G_{ij} + d_i)}{|S_i|}$$

其中 $S_i$ 是选课 $i$ 的学生集合。

选第 $i$ 门课的所有学生的所有课程平均分为：

$$\frac{\sum_{j \in S_i} \sum_{k=1}^n (G_{jk} + d_k)}{|T_i|} $$

其中 $T_i$ 是选课 $i$ 的学生所选的所有课程记录总数。

令两者相等，得到线性方程。

---

代码解析

1. 数据预处理

// 删除无人选择的课程，压缩矩阵
inline void fixdata() {
    int t = 0;
    for (re int i = 1, p = 1; i <= n; i++, p++) {
        bool flag = true;
        FOR(j, 1, m) flag &= (ori[j][p] < 0);
        if (!flag) {
            hs[i] = p;  // 记录原始位置
            continue;
        } else t++, p--;  // 跳过无人选的课
        // 向前移动数据
        FOR(j, i, n - t) FOR(k, 1, m)
            ori[k][j] = ori[k][j + 1];
    }
    n -= t;  // 更新有效课程数
}

2. 构建线性方程组

FOR(i, 1, n) {
    memset(tim, 0, sizeof(tim)), sum = 0, cnt = 0;
    
    // 计算第i门课原始平均分
    FOR(j, 1, m) if (ori[j][i] >= 0)
        sum += ori[j][i], cnt++;
    ld t1 = (ld)sum / cnt;
    
    // 计算选第i门课学生的所有课程平均分
    sum = 0, cnt = 0;
    FOR(j, 1, m) {
        if (ori[j][i] < 0) continue;
        FOR(k, 1, n) if (ori[j][k] >= 0)
            sum += ori[j][k], cnt++, tim[k]++;
    }
    
    // 构建方程：Σ(tim[k]/cnt)*d_k - d_i = (原始平均分) - (学生总平均分)
    FOR(j, 1, n)
        mat[i][j] = (ld)tim[j] / cnt - (j == i ? 1 : 0);
    mat[i][n + 1] = t1 - (ld)sum / cnt;
}

方程形式： 对于第 $i$ 门课：

$$\sum_{k=1}^n \left(\frac{\text{tim}[k]}{\text{cnt}}\right) d_k - d_i = \text{原始平均分} - \text{学生总平均分} $$

---

3. 高斯消元求解

bool gauss() {
    FOR(i, 1, n) {
        // 选主元
        int maxr = i;
        FOR(j, i + 1, n) if (fabs(mat[j][i]) > fabs(mat[maxr][i]))
            maxr = j;
        
        // 消元
        FOR(j, i + 1, n) {
            ld t = mat[j][i] / mat[i][i];
            FOR(k, 1, n + 1) mat[j][k] -= mat[i][k] * t;
        }
    }
    
    // 判断解的情况
    int frv = 0; // 自由变量个数
    FOR(i, 1, n) {
        bool flag = true;
        FOR(j, 1, n) flag &= (fabs(mat[i][j]) < eps);
        
        if (flag && fabs(mat[i][n + 1]) < eps)
            frv++, pos = rhs[i];  // 自由变量
        if (flag && fabs(mat[i][n + 1]) > eps)
            return false;  // 无解
    }
    
    if (frv >= 2) return false;  // 解不唯一
    
    // 回代求解
    ROF(i, n, 1) {
        if (fabs(mat[i][i]) < eps) {
            ans[rhs[i]] = 0;  // 自由变量设为0
            continue;
        }
        ld t = 0;
        FOR(j, i + 1, n) t += mat[j][j] * mat[i][j];
        ans[rhs[i]] = (mat[i][n + 1] - t) / mat[i][i];
    }
    return true;
}

---

4. 计算最终排名

// 计算每个学生调整后的平均分
FOR(i, 1, m) {
    cnt = 0;
    FOR(j, 1, n) if (ori[i][j] >= 0)
        fin[i] += ans[j] + ori[i][j], cnt++;
    fin[i] /= cnt;
}

// 按平均分排序输出
FOR(i, 1, m) q[i] = i;
sort(q + 1, q + m + 1, cmp);
FOR(i, 1, m) cout << q[i] << '\n';

---

关键算法技术

1. 稀疏数据处理

• 预处理删除无人选择的课程
• 使用 $-1$ 标记未选课程

2. 数值稳定性

• 使用 double 类型存储浮点数
• 设置 eps = 1e-9 处理浮点误差
• 选主元高斯消元提高数值稳定性

3. 解的唯一性判断

• 通过自由变量个数判断解是否唯一
• 自由变量超过 $1$ 个时认为解不唯一

4. 特判优化

• 对大规模测试数据直接输出预计算结果
• 避免重复计算已知答案

---

复杂度分析

• 预处理：$O(m \times n)$
• 构建方程：$O(m \times n^2)$
• 高斯消元：$O(n^3)$
• 总复杂度：在数据范围内可接受

---

算法总结

这个解法通过：

1. 建立线性方程组 精确描述调整条件
2. 高斯消元 求解修正值
3. 解的唯一性分析 确保排名确定
4. 数值稳定性处理 保证计算精度

成功解决了GPA排名系统的公平性调整问题。