题解 P1404 【平均数】

· · 题解

二分答案自然是平均数一类问题的常用思路。不过这题还有O(n)的算法（参见2004年集训队论文，周源）

大体思路是先求部分和S(x)，然后连续子序列平均值就转化为S-x平面上的斜率：ave(x,y)=(S(y)-s(x-1))/(y-x+1)。考虑x<y<z的三个点如果S(y)是上凸的，则这个点一定没贡献。所以有用的点构成一个下凸的折线

用一个队列维护这个折线，加入新点时（如当前点为i，则新点为i-m），如果与队尾2个点形成上凸，则删除队尾点。如果队首2个点与当前点形成上凸，同理删除队首点。最后每次队首元素都是与点i斜率最大的点，再求最值就行了

#include <iostream>
#include <cmath>
#define N 100005
typedef long long ll;
using namespace std;

ll n,m,s[N];
double ans=0.0;
ll q[N],t,h;   // 队列

double k(ll x,ll y){  // 计算s[x],s[y]的斜率
    return (s[y]-s[x]+0.0)/(y-x);
}

int main() {
    cin>>n>>m;
    for (ll i=1,x;i<=n;i++){
        cin>>x; s[i]=s[i-1]+x;
    }

    for (ll i=m;i<=n;i++){
        while (t-h>=2 && k(i-m,q[t-1])<k(i-m,q[t-2])) t--;   // 删除上凸点
        q[t++]=i-m;  // 入队
        while (t-h>=2 && k(i,q[h])<k(i,q[h+1])) h++;  // 移动最大斜率点
        ans=max(ans,k(i,q[h]));
    }

    cout<<(ll)floor(ans*1000)<<endl;
    return 0;
}

这个方法还可以求以每个点结尾的满足条件的最大平均数，这样子二分答案就不行啦，hoho~~