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;
}
牛客暑期多校训练营题解 文章被收录于专栏

收集牛客暑期多校训练营的题解

全部评论

相关推荐

秋招倒计时了,有没有一起组队捡漏的?
牛客965593684号:我倒是觉得捡漏机会不多,现在大厂都精得很,超发一大堆offer,还是等春招吧
点赞 评论 收藏
分享
10-07 23:57
已编辑
电子科技大学 Java
八街九陌:博士?客户端?开发?啊?
点赞 评论 收藏
分享
你是来当牛马的吧:行了,照片拍完了,让大家都回工位吧
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务