2020牛客暑期多校训练营（第六场）C

题目描述

Roundgod has an $n \times m$ matrix $A = (a_{ij})$ . One day while she's doing her physics homework, she wonders is it possible to define the physical quantity for matrices.
As we all know, the pressure $p$ satisfies a formula $p=\frac{F}{S}$ , where $F$ is the compressive force and $S$ is the base area.
To describe it in maths, Roundgod puts forward that the compressive force of a matrix equals the sum of all its entries, while the base area of a matrix equals the sum of the entries in its last row. Then she can calculate the pressure for a matrix with the same formula.
Your goal is to find the submatrix of AA with maximum pressure.
A submatrix is obtained by taking nonempty subsets of its rows and columns. Formally, given a nonempty subsequence $S$ of $\{1,2, \ldots, n\}$ and a nonempty subsequence $T$ of $\{1, 2, \ldots, m\}$ , then $\begin{pmatrix} a_{S_1, T_1} & a_{S_1, T_2} & \cdots & a_{S_1, T_{|T|}} \\ a_{S_2, T_1} & a_{S_2, T_2} & \cdots & a_{S_2, T_{|T|}} \\\vdots & \vdots & \ddots & \vdots \\ a_{S_{|S|}, T_1} & a_{S_{|S|}, T_2}&\cdots & a_{S_{|S|}, T_{|T|}} \end{pmatrix}$ is a submatrix of $A$ .

输入描述

There are multiple test cases. The first line of input contains an integer $T\ (T\leqslant 100)$ , indicating the number of test cases. For each test case:
The first line contains two integers $n, m\ (1\leqslant n,m\leqslant 200)$ , the number of rows and columns of the matrix, respectively.
Each of the next $n$ lines contains $m$ integers, specifying the matrix $(1\leqslant a_{ij}\leqslant 5\times 10^4)$ .

输出描述

For each test case, print the maximum pressure within an absolute or relative error of no more than $10^{-8}$ in one line.

示例1

输入

输出

4.50000000

说明

$\begin{pmatrix}1 & 5\\6 & 9 \\2 & 4\end{pmatrix}$ is one of submatrices of $A$ with maximum pressure $\frac{1+5+6+9+2+4}{2+4}=\frac{27}{6}=4.5$ .

分析

$\forall\ a,b,c,d\in \mathrm N^\ast$ ，若 $\frac{a}{b}\leqslant \frac{c}{d}$ ，那么 $\frac{a}{b}\leqslant\frac{a+b}{c+d}\leqslant\frac{c}{d}$ 。因此，若选择的子矩阵有多列，将其拆成两个行数相同的更小的子矩阵，一定有一个小子矩阵的压强大于等于原子矩阵的压强。所以，最优的子矩阵应当只有一列。
若 $a_{ij}$ 为一个子矩阵的底面积，贪心地取 $a_{1j},a_{2j},\cdots,a_{ij}$ 为子矩阵（ $a_{ij}$ 正上方的所有元素），其压强是所有以 $a_{ij}$ 为底面积的子矩阵中压强最大的。枚举 $a_{ij}$ ，即可在 $O(nm)$ 内求得答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem C
Date: 8/26/2020
Description: Inequality
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=202;
int _;
int n,m;
int a[N][N];
double sum[N][N];
int main(){
    for(cin>>_;_;_--){
        scanf("%d%d",&n,&m);
        int i,j;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
            }
        }
        //预处理每一列的前缀和
        for(j=1;j<=m;j++){
            for(i=1;i<=n;i++){
                sum[j][i]=a[i][j]+sum[j][i-1];
            }
        }
        double ans=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                ans=max(ans,sum[j][i]/a[i][j]);
            }
        }
        printf("%.8lf\n",ans);
    }
    return 0;
}