挖金矿 题解【分数规划】【二分答案】

作者: wjyyy 分类: 二分,分数规划,解题报告 发布时间: 2018-07-26 15:28

点击量:19

 

题目可提交地址: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;
}

说点什么

avatar
  Subscribe  
提醒
/* */