2020牛客暑期多校训练营(第六场)C
Combination of Physics and Maths
https://ac.nowcoder.com/acm/contest/5671/C
题目描述
Roundgod has an matrix . 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 satisfies a formula , where is the compressive force and 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 of and a nonempty subsequence of , then is a submatrix of .
输入描述
There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:
The first line contains two integers , the number of rows and columns of the matrix, respectively.
Each of the next lines contains integers, specifying the matrix .
输出描述
For each test case, print the maximum pressure within an absolute or relative error of no more than in one line.
示例1
输入
1 3 3 1 3 5 6 8 9 2 7 4
输出
4.50000000
说明
is one of submatrices of with maximum pressure .
分析
,若 ,那么 。因此,若选择的子矩阵有多列,将其拆成两个行数相同的更小的子矩阵,一定有一个小子矩阵的压强大于等于原子矩阵的压强。所以,最优的子矩阵应当只有一列。
若 为一个子矩阵的底面积,贪心地取 为子矩阵( 正上方的所有元素),其压强是所有以 为底面积的子矩阵中压强最大的。枚举 ,即可在 内求得答案。
代码
/****************************************************************** 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; }
收集牛客暑期多校训练营的题解