【JZOJ4809】【NOIP2016提高A组五校联考1】挖金矿

题目描述

输入

输出

样例输入

4 3

4 3 3

5 1 6

2 6 1

3 2 9

样例输出

4.4286

数据范围

样例解释

解法

二分答案。

对于答案ans，如果每一列的最大贡献之和大于0，则ans合法；

每一列的最大贡献= max(a[1..i]−i∗ans) ，其中 1<=i<=m 。

代码

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define ln(x,y) ll(log(x)/log(y))
#define sqr(x) ((x)*(x))
using namespace std;
const char* fin="aP1.in";
const char* fout="aP1.out";
const ll inf=;
const ll maxn=;
ll n,m,i,j,k,tot;
double ans,l,r,mid;
ll a[maxn];
bool judge(double v){
    int i,j,k;
    double tmp,tmd,maxx,sum=;
    for (i=;i<=n;i++){
        tmp=tmd=maxx=;
        bool bz=false;
        for (j=;j<=m;j++){
            tmp+=a[(i-)*m+j];
            tmd+=v;
            if (!bz || maxx<tmp-tmd){
                bz=true;
                maxx=tmp-tmd;
            }
        }
        sum+=maxx;
    }
    return sum>=;
}
int main(){
    scanf("%d%d",&n,&m);
    tot=n*m;
    for (i=;i<=tot;i++){
        scanf("%d",&a[i]);
    }
    l=;
    r=;
    while (r-l>){
        mid=(l+r)/;
        if (judge(mid)) l=mid;
        else r=mid;
    }
    printf("%.4lf",l);
    return ;
}
           

启发

求平均数可以使用二分把问题转化为判定性问题。