挖金矿

2024-07-10 14:56| 来源: 网络整理| 查看: 265

挖金矿题目背景

矿工吉丽得到了一个任务：挖金矿！

题目描述

这是一个深度为\(h\)，宽度为\(n\)的矿场。吉丽站在地面上，第\(i\)层第\(j\)列有价值为\(a[i][j]\)的金矿。如图是一个\(h\times n\)的矩阵，左上角为\((1,1)\)右下角为\((h,n)\)。

对于每一列，吉丽可以选择向下挖\(k(1\le k\le n)\)层。

吉丽希望挖到的金矿的平均价值最大，请你告诉他答案。

输入输出格式输入格式：

第一行，两个整数，\(n,h\)。接下来\(n\)行，每行\(h\)个数，第\(i+1\)行第\(j\)个数表示的是\(a[j][i]\)

输出格式：

输出挖出金矿的最大平均价值，保留3位小数。

数据规模与约定：

对于30%的数据，\(h\times n\le 100,1\le a[i][j]\le 100\)；

对于100%的数据，\(h\times n\le 10^5,1\le a[i][j]\le 10^9\)。

思路：二分平均值，对全图每个点减去平均值后，每次取某一列的最大值，看结果是否小于0

本质上是分数规划问题

Code:

#include #include using namespace std; const int N=100010; vector a[N]; int n,m; double l=0,r=0; bool check(double d) { double mx,f,sum=0; for(int i=1;i=0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i

【本文地址】

公司简介

联系我们