Brief description:

读入一列正数N，a1, a2, …, aN，以及一个数F。
定义ave(i,j) = ai 到 aj 的平均值, 要求 j-i+1 >= k，
求一个最大的ave（i，j）

Analysis:

。。每次询问固定一点 (x, y) 与之前某点所形成直线的最大斜率。
单调队列维护下凸壳即可（x 单调）。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
int s[N], q[N], cz, op;
int n, k;

LL det(LL x0, int y0, LL x1, int y1){
    return x0*y1 - x1*y0;
}

int dett(int p0, int p1, int p2){
    LL t = det(p1-p0, s[p1]-s[p0], p2-p0, s[p2]-s[p0]);
    return t < 0 ? -1 : t > 0;
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d %d", &n, &k)){
        REP_1(i, n) s[i] = s[i-1] + RD();

        DB z = 0; cz = 0, op = -1; FOR_1(i, k, n){
            int ii = i-k;
            while (cz < op && dett(q[op-1], q[op], ii) <= 0) --op; q[++op] = ii;
            while (cz < op && dett(q[cz], q[cz+1], i) >= 0) ++cz;
            checkMax(z, (DB)(s[i] - s[q[cz]] ) / (i - q[cz]));
        }
        OT(z);
    }
}

http://www.cnblogs.com/Free-rein/archive/2012/08/09/2630190.html
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2798173

Posted by xiaodao
Category: 日常