点击量：244

题目可提交地址：https://www.luogu.org/problemnew/show/U31832

目录

题目背景

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

 

题目描述

这是一个深度为$ 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位小数。

 

输入输出样例

输入样例#1：

4 3
4 3 3
5 1 6
2 6 1
3 2 9

输出样例#1：

4.429

说明

样例解释：

如图是一种合法方案，吉丽决定每一列分别挖$ 1,1,2,3$层。涂色的格子代表吉丽选择挖的金矿，价值平均值为$ (4+5+2+6+3+2+9)/7=31/7\approx 4.429$,可以证明，这是最大的。

 

数据规模与约定：

对于$ 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$。

题解：

    一开始做这个题会发现怎么贪都贪不对，于是考虑到最终答案是与挖矿格数相关联的，于是想到了分数规划。这个题的答案就是$ \frac{\sum\limits_{i=1}^{n\times k}a_i\times x_i}{\sum x_i}$。其中$ x_i$为0或1，决定选或不选。而这个题中只有上面选了下面才能选，因此对每一列，我们选择贡献最大的的上面$ k$个。如何判断贡献最大，我们要对上面的式子变形。

    设$ \frac{\sum\limits_{i=1}^{n\times k}a_i\times x_i}{\sum x_i}=L$

    则$ L\cdot \sum x_i=\sum\limits_{i=1}^{n\times k}a_i\times x_i$

    要使L最大，就要二分找出它的最大值，因为分数规划就是要二分答案，通过检验另一端的最大值来判断L的大小。因此在出现分数的题目中，要多想想分数规划，也就是检验答案的合法性。

    在这个题中还要注意的就是只给出了数据规模的乘积，因此我们用一维数组根据下标来访问这些值就可以了。

Code：

#include<cstdio>
#include<cstring>
#define eps 1e-7
double max(double a,double b){return a>b?a:b;}
int n,h;
long long a[101000];
bool check(double x)
{
    double sum=0;
    for(int i=1;i<=n;i++)
    {
        double mx=-1e20;//应该是必须挖
        for(int j=1;j<=h;j++)
            mx=max(mx,a[(i-1)*h+j]-a[(i-1)*h]-j*x);
        sum+=mx;
    }
    return sum>=0;
}
int main()
{
    scanf("%d%d",&n,&h);
    double sum=0.0;
    int tot=0;
    for(int i=1;i<=n*h;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
    }
    double l=0.0,r=a[n*h]*1.0,mid;
    while(r-l>=eps)
    {
        mid=(l+r)/2.0;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%.3lf\n",l);
    return 0;
}