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

挖金矿

题目大意

给出一个n行h列的矩阵，每一行可以选择前 k个数(1<=k<=h)，求选出的数的平均数的最大值（答案保留4位小数）。

数据范围

n*h<=105且矩阵中的数都为不超过109的非负正整数。

题解

看到求平均数的最大值，优先考虑二分。
二分答案，用矩阵里的数减去二分的答案~~，若为正数，说明比二分的答案大，若为负数，说明比二分的答案小，然而这结论并没有什么卵用~~，对于每一行都做一次前缀和，然后对于每一行选最大的前缀和加入贡献当中，若总贡献大于0，则说明这个二分值可行，二分上调，反之二分下调。（这种做法的正确性十分显然，证明略，请读者自行思考，注意精度）

Code(Pascal)

var
    a:array[0..350000] of extended;
    n,h,l,i:longint;
    le,ri,mi:extended;
function maxe(a,b:extended):extended;
    begin
        if a>b then exit(a)
        else exit(B);
    end;
function ok(oo:extended):boolean;
    var
        cqy,lo,ve:extended;
        i,l,k:longint;
    begin
        lo:=0;
        cqy:=0;
        k:=0;
        for i:=1 to n do
        begin
            lo:=0;
            ve:=-maxlongint;
            for l:=1 to h do
            begin
                inc(k);
                lo:=lo+a[k]-oo;
                ve:=maxe(ve,lo);
            end;
            cqy:=cqy+ve;
        end;
        if cqy>=0 then exit(true)
        else exit(false);
    end;
begin
    readln(n,h);
    for i:=1 to n do
    begin
        for l:=1 to h do
        read(a[i*h-h+l]);
        readln;
    end;
    le:=0;
    ri:=1000000000;
    while le+0.0000001<ri do
    begin
        mi:=(le+ri)/2;
        if ok(mi) then le:=mi
        else ri:=mi;
    end;
    while not(ok(le)) do le:=le-0.00001;
    writeln(le:0:4);
end.