3079金鉱を掘る

Task N*mの矩形は、行ごとに[1,m]の個数をとり、取り出した最大平均値を求める.
H*n<=1e5,a[i][j]∈[1,1e9]
Solution二分の機能:①秩序配列ある値を探す②仮定解、③最小値を最大化する④平均値を最大化する本題用2,4の機能.
sum1+sum2+*+sumn/num1+num2+***numn>=k (sum1-k*num1)+(sum2-k*num2)+*(sumn-k*numn)>=0
この行を順次スキャンし、sum-k*numの最大値をこの行の選択として見つけます.
Doubleタイプの二分テクニック:100回ループし、midをlまたはrに割り当てます.lがr+0.00001より小さいと止められるので、私のように750回もバカに循環しないでください.TLEを招きました.
よく見られる最大化平均値には、列挙+貪欲/dp列挙分子があり、貪欲分母であるが、これはこの問題には適用されない.
code

const int M=1e5+5;
vector<int>A[M];
int n,m,mx;
inline void input(){
    int i,j,k;
    rd(n);rd(m);
    rep(i,0,n-1)rep(j,1,m)rd(k),A[i].pb(k),mx=max(mx,k);
}
inline bool check(db k){
    int i,j;ll sum=0;
    db ans=0.0,mx;
    rep(i,0,n-1){   
        mx=-2e9;sum=0;
        rep(j,0,m-1){
            sum+=A[i][j];
            mx=max(mx,(db)sum-1.0*1ll*k*(j+1));
        }
        ans+=mx;
    }
    return ans>=0;
}
inline void solve(){
    int i,j,k=50;
    db l=0,r=1.0*mx;
    db mid;
    while(k--){
        mid=1.0*(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.4lf
",l);
}
int main(){
    input();
    solve();
    return 0;
}