2020牛客多校第六场 C. Combination of Physics and Maths（等比定理）
African Sort
https://ac.nowcoder.com/acm/contest/5671/A
题意：定义矩阵的压强为 所有元素的和 / 最后一行的和。给一个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;
}
不喜勿喷，可以叫我删除
