挖金矿

题目背景

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

题目描述

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

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

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

输入输出格式

输入格式：

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

输出格式：

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

数据规模与约定：

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

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

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

本质上是分数规划问题

Code:

#include <cstdio>
#include <vector>
using namespace std;
const int N=100010;
vector <double> a[N];
int n,m;
double l=0,r=0;
bool check(double d)
{
    double mx,f,sum=0;
    for(int i=1;i<=n;i++)
    {
        mx=-d,f=0;
        for(int j=0;j<a[i].size();j++)
        {
            f+=a[i][j]-d;
            mx=mx>f?mx:f;
        }
        sum+=mx;
    }
    return sum>=0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            double t;
            scanf("%lf",&t);
            a[i].push_back(t);
            r=r>t?r:t;
        }
    while(l+1e-4<r)
    {
        double mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%.3lf
",l);
    return 0;
}

2018.7.25