题意:定义矩阵的压强为 所有元素的和 / 最后一行的和。给一个n * m的矩阵,选取若干行和若干列,相交位置的元素提出来作为子矩阵,问所有子矩阵的最大压强
思路:若从原矩阵中选一行作为子矩阵的最后一行,为了使压强最大,选中列在该行上面的所有元素肯定都要选中,即行的选取一定是从第一行到某一行都选;若有两列的压强分别为a / b,c / d,且a / b >= c / d,那么有 a / b >= (a + c) / (b + d) >= c / d,即最优解一定是单列,所以 n ^ 2 扫一遍就好了
-----------------------------------------证明-----------------------------------------
已知 ,证明
(下面转自https://blog.csdn.net/puss0/article/details/103778756
-----------------------------------------------------------------------------------------
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 205; int a[N]; int main() { int t, n, m, x; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); memset(a, 0, sizeof(a)); double ans = 0.0; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { scanf("%d", &x); a[j] += x; ans = max(ans, 1.0 * a[j] / x); } } printf("%.8f\n", ans); } return 0; }