P10450 [USACO03MAR] Best Cow Fences G 题解

· · 题解

前言

本题几乎全部题解（除了 https://www.luogu.com.cn/article/4uf80r82 使用的是斜率优化）都使用的是二分。时间复杂度为 O(n \log W)。

但是本题可以实现 O(n) 的复杂度。不过只有唯一一篇题解提及了这种做法（就是前文提到的那篇），而且说得比较含糊。于是便有了本文。

思路

令序列 s 为 A 的前缀和。

那么以 i 结尾的区间最大平均数是：

\frac{s_i-s_j}{i-j}

其中，0 \le j \le (i-L)。

我们将每个点对应到坐标轴上。对于 i，其横坐标为 i，纵坐标为 s_i。

那么上面的公式其实就是计算点 i,j 所在直线的斜率。

我们又知道，0 \le A_i，所以 s 满足单调不下降。

转换一下问题，相当于求两个点之间的最大斜率。因此，我们可以使用斜率优化实现 O(n) 复杂度。

实现

用单调队列实现。

再次强调，因为 0 \le A_i，所以 s 满足单调不下降。也就是说，任意两个点所在的直线斜率不会是负数。单调队列是正确的。

单调队列的主要操作是“掐头去尾”。

首先讨论弹出队头的情况：

如图，设最右边的点是即将加入队列的点。黄线的斜率大于蓝线的斜率，因此这个点的答案肯定不会是蓝线。所以蓝线就可以弹出了。

如图，黄线的斜率小于蓝线的斜率，这个点的答案可能是蓝线。因此不应该弹出。

这个点的最终答案就是该点与队头所在直线的斜率。

接下来讨论弹出队尾的情况：

图中绿色的点是队列中的点。这些点构成了下凸壳。将这些点从后往前依次跟红色点（待讨论的点）进行比较。

图中蓝线是不合法的。因为蓝线跟黑线不能组成下凸壳。这样的情况应该将对应点弹出。黄线是第一条合法的线。

以此规则维护即可。

注意区间长度最小为 L。以及恶心的精度。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
double ans = 0;
double num[100005],sum[100005];
double slope(int x,int y){
    return (sum[x]-sum[y])/(x-y);
}
int Head,End;
int que[100005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%lf",&num[i]);
        sum[i] = sum[i-1]+num[i];
    }
    Head = 0,End = 0;
    for(int i = m; i <= n; i++){
        while(Head < End && slope(i,que[Head]) <= slope(i,que[Head+1])){//弹出队头
            Head++;
        }
        ans = max(ans,slope(i,que[Head]));
        while(Head < End && slope(que[End],que[End-1]) >= slope(i-m+1,que[End])){//弹出队尾
            End--;
        }
        End++;
        que[End] = i-m+1;
    }
    int tp;
    tp = ans*1000;
    if(tp%10 == 7){//可恶的精度！神秘数据不给 SPJ，只能特判
        tp--;
    }
    printf("%d",tp);
    return 0;
}