Combination of Physics and Maths - 题解

标签与难度

标签: 分数规划, 贪心, 数学, 思维题, 矩阵, 前缀和 难度: 1600

题目大意喵~

一位叫 Roundgod 的同学对物理和数学的结合产生了奇思妙想，喵~ 她为一个 $n \times m$ 的矩阵 $A$ 定义了一个叫做“压强”的物理量。

这个压强的计算公式是 $p = \frac{F}{S}$，其中：

• 压力 (Force, $F$): 定义为矩阵中所有元素的总和。
• 底面积 (Base Area, $S$): 定义为矩阵最后一行所有元素的总和。

我们的任务是，从给定的 $n \times m$ 矩阵 $A$ 中，通过选择一部分行和一部分列（都不能为空集），构成一个子矩阵，并让这个子矩阵的“压强”达到最大值。

一个子矩阵是通过选择原矩阵的行下标的非空子序列 $S_{rows}$ 和列下标的非空子序列 $T_{cols}$ 得到的。子矩阵的“最后一行”就是指在 $S_{rows}$ 中，原始行号最大的那一行哦！

举个栗子：如果我们选了第1、3行和第2、5列，那么子矩阵的“最后一行”就是原矩阵的第3行中，属于第2、5列的那些元素组成的行，呐。

解题思路分析

喵哈~ 这道题看起来是要我们在茫茫多的子矩阵中找到一个最优的，感觉会很复杂的样子。但是不要怕，让我带你一步一步解开它的谜底！

首先，我们把压强的公式写出来。假设我们选择的行号集合是 $S_{rows}$，列号集合是 $T_{cols}$。设 $r_{last} = \max(S_{rows})$ 是我们所选行中，在原矩阵里行号最大的那一行。那么压强就是：

$$p = \frac{\sum_{i \in S_{rows}} \sum_{j \in T_{cols}} a_{i,j}}{\sum_{j \in T_{cols}} a_{r_{last}, j}}$$

这个公式看起来好吓人，有好多变化的量。当遇到这种多变量优化问题时，一个很有效的技巧就是“控制变量法”，或者叫“降维打击”！我们先固定一个变量，看看问题会变成什么样，喵~

第一步：固定“最后一行”

我们不妨枚举子矩阵的“最后一行”是原矩阵的哪一行。假设我们钦定第 $k$ 行为子矩阵的“最后一行”（$k$ 从 $1$ 到 $n$）。

既然第 $k$ 行是最后一行，那么我们选择的行号集合 $S_{rows}$ 必须包含 $k$，并且集合里其他所有行号都必须小于等于 $k$。也就是说，$S_{rows} \subseteq \{1, 2, \ldots, k\}$ 且 $k \in S_{rows}$。

现在，对于固定的最后一行 $k$ 和固定的列集合 $T_{cols}$，我们应该如何选择 $S_{rows}$ 中的其他行呢？ 我们的目标是最大化 $p$。观察公式，分母 $\sum_{j \in T_{cols}} a_{k, j}$ 已经由 $k$ 和 $T_{cols}$ 确定了。为了让分数变大，我们自然希望分子 $\sum_{i \in S_{rows}} \sum_{j \in T_{cols}} a_{i,j}$ 越大越好！

题目中的元素值（根据样例和常识推断）都是正数。所以，要想让分子最大，我们应该把所有能选的行都选上！也就是说，我们应该把第 $1$ 行到第 $k-1$ 行全部都选入 $S_{rows}$。

这样，我们的第一个关键简化就出现啦：如果一个子矩阵的最后一行是原矩阵的第 $k$ 行，那么要使其压强最大，这个子矩阵的行集合必然是 $\{1, 2, \ldots, k\}$。

第二步：固定了行，再来看列

经过第一步的分析，问题被简化为：对于每一个 $k \in \{1, \ldots, n\}$，考虑由前 $k$ 行构成的子矩阵，我们应该如何选择列集合 $T_{cols}$ 来最大化压强？

此时，对于一个固定的 $k$，压强公式变成了：

$$p_k(T_{cols}) = \frac{\sum_{j \in T_{cols}} \left(\sum_{i=1}^{k} a_{i,j}\right)}{\sum_{j \in T_{cols}} a_{k, j}}$$

为了方便，我们定义两个量：

• $C_j^{(k)} = \sum_{i=1}^{k} a_{i,j}$：第 $j$ 列从第 1 行到第 $k$ 行的元素之和。
• $B_j^{(k)} = a_{k, j}$：第 $j$ 列在第 $k$ 行的那个元素值。

于是公式可以写成：

$$p_k(T_{cols}) = \frac{\sum_{j \in T_{cols}} C_j^{(k)}}{\sum_{j \in T_{cols}} B_j^{(k)}}$$

这其实是一个经典的分数规划模型！我们要选择一个非空列集合 $T_{cols}$ 来最大化这个比值。

第三步：最终的洞察！

让我们来思考一下这个分数的性质。它其实是一个加权平均值！我们可以把它看成是对每个被选中的列 $j \in T_{cols}$ 的“单位压强” $r_j = \frac{C_j^{(k)}}{B_j^{(k)}}$ 进行加权平均，权重就是 $B_j^{(k)}$。

$$p_k(T_{cols}) = \frac{\sum_{j \in T_{cols}} B_j^{(k)} \cdot \frac{C_j^{(k)}}{B_j^{(k)}}}{\sum_{j \in T_{cols}} B_j^{(k)}}$$

一个重要的数学常识是：一组数的加权平均值，永远不会超过这组数中的最大值。

打个比方，喵~ 假设你有几种猫粮，每种的“美味度/克”都不同。无论你怎么混合它们，混合后的猫粮的“美味度/克”也绝对不会超过其中最美味的那一种，对吧？

所以，对于固定的最后一行 $k$，无论我们怎么选取列的组合 $T_{cols}$，其压强 $p_k(T_{cols})$ 都不会超过所有单列压强的最大值。

$$p_k(T_{cols}) \le \max_{j \in T_{cols}} \left\{ \frac{C_j^{(k)}}{B_j^{(k)}} \right\} \le \max_{j \in \{1, \ldots, m\}} \left\{ \frac{C_j^{(k)}}{B_j^{(k)}} \right\}$$

这意味着，要取得最大压强，我们根本不需要组合多个列！我们只需要选择那个能提供最大“单位压强”的单列就可以了！

最终的算法

这下思路就完全清晰了，喵~ 我们的最终算法是：

1. 初始化一个全局最大压强 max_pressure = 0.0。
2. 为了高效计算 $C_j^{(k)}$，我们用一个数组 column_sums 来记录每一列的元素前缀和。column_sums[j] 表示第 $j$ 列从第 1 行到当前行的和。
3. 我们从第 1 行遍历到第 $n$ 行，把当前行 k 当作“最后一行”。 a. 对于每一列 j，我们更新 column_sums[j]，加上当前元素 a[k][j]。 b. 然后，我们计算只选择第 j 列时的压强：pressure_kj = column_sums[j] / a[k][j]。 c. 用这个 pressure_kj 来更新我们的全局最大压强 max_pressure。
4. 遍历完所有行之后，max_pressure 就是我们要求的答案啦！

这个算法只需要遍历一次矩阵，非常高效，呐！

代码实现

这是我根据上面的思路，精心重构的一份代码，注释超详细的哦！

#include <iostream>
#include <vector>
#include <iomanip> // 用于设置输出精度 setprecision
#include <numeric> // 用于 std::accumulate (虽然这里没用，但是好用的说)
#include <algorithm> // 用于 std::max

// 使用 using namespace std; 在竞赛中很方便，但在大项目中要小心哦
using namespace std;

// 定义一个解决单次询问的函数，让主函数更整洁
void solve() {
    int n, m;
    cin >> n >> m;

    // 读入整个矩阵
    // 使用 long long 来防止元素值和它们的和溢出，这是个好习惯喵
    vector<vector<long long>> matrix(n, vector<long long>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }

    // 用于存储每一列从第0行到当前行的元素和 (前缀和)
    // 就像一个滚动的小货车，每经过一行就装上那一行对应列的货物
    vector<long long> column_sums(m, 0);

    // 全局最大压强，初始化为一个很小的值
    double max_pressure = 0.0;

    // 遍历每一行，将当前行 i 视为子矩阵的“最后一行”
    for (int i = 0; i < n; ++i) {
        // 遍历每一列
        for (int j = 0; j < m; ++j) {
            // 更新第 j 列的元素和
            column_sums[j] += matrix[i][j];

            // 计算以第 i 行为底，只选择第 j 列构成的子矩阵的压强
            // 分子 F: 第 j 列从第 0 行到第 i 行的总和
            long long force = column_sums[j];
            // 分母 S: 第 j 列在第 i 行的元素值
            long long base_area = matrix[i][j];

            // 计算压强，注意要转换成 double 类型进行浮点数除法
            double current_pressure = static_cast<double>(force) / base_area;

            // 看看这个压强是不是我们遇到的最大的？
            if (current_pressure > max_pressure) {
                max_pressure = current_pressure;
            }
        }
    }

    // 输出最终答案，并设置精度
    cout << fixed << setprecision(8) << max_pressure << endl;
}

int main() {
    // 加速输入输出，对付大数据量很有用！
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N \times M)$。 我们用两层嵌套循环遍历了整个 $N \times M$ 的矩阵一次。在循环内部的所有操作（加法、除法、比较）都是常数时间 $O(1)$ 的。所以总的时间复杂度和读取输入的时间复杂度相同，是 $O(N \times M)$，非常高效！

• 空间复杂度: $O(M)$。 我们主要使用了额外的空间来存储 column_sums 数组，它的大小和矩阵的列数 $M$ 相同。因此，空间复杂度是 $O(M)$。如果算上输入矩阵本身，那就是 $O(N \times M)$，但通常我们只考虑算法运行所需的额外空间，所以是 $O(M)$。

知识点总结

这道题虽然披着物理的外衣，但核心是纯纯的数学和算法思维，喵~

1. 问题简化与降维: 面对多变量的复杂优化问题，尝试固定一部分变量（比如本题中的“最后一行”），将问题分解成更简单的子问题，是一种非常强大和常用的解题策略。

2. 分数规划 (Fractional Programming) 的直觉: 本题的核心是最大化一个形如 $\frac{\sum C_j}{\sum B_j}$ 的比值。通过理解它是一个加权平均，我们得出了“整体最优解蕴含于个体最优之中”的结论，即最大值一定在只选择单个“最优个体”（单列）时取到。这避免了复杂的组合搜索或排序。

3. 前缀和思想: 使用 column_sums 数组来动态维护列的和，避免了在每次计算压强时都重复从头加到尾。这是一种经典的空间换时间技巧，将每次求和的 $O(N)$ 复杂度降为了 $O(1)$ 的更新。

希望这篇题解能帮助你更好地理解这道有趣的题目！继续加油，算法的世界还有更多宝藏等着我们去发现呢，喵~