链接：https://ac.nowcoder.com/acm/contest/942/D
来源：牛客网
 

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

小A出了一道只有题目和计算几何有关的题
给出整数数组A，求长度大于等于L的连续子段中，平均数最大的那个。输出平均数。

输入描述:

 

 

 

输出描述:

一行一个数表示答案，你的答案正确当且仅当和标准答案误差不超过10−6

示例1

输入

复制

5 2
3 7 5 5 16

输出

复制

-0.50000000

说明

序列为3,−4,−4,−7,0

备注:

对于10%10%的数据，L=1L=1
对于20%20%的数据，n≤1000n≤1000
对于40%40%的数据，n≤105n≤105
对于另外20%20%的数据，m≤10,L≤105m≤10,L≤105
对于100%100%的数据，1≤L≤n≤1071≤L≤n≤107，1≤a1,x,y,z,m≤1091≤a1,x,y,z,m≤109，mm为偶数

和POJ  2018  相仿  

利用斜率优化  求解

参考2004年论文  周源--浅谈数形结合思想在信息学竞赛中的应用.

取Pt点之前凸包的最大斜率处，

删除之前点

将和Pt距离为L的点加入

删除前面不符合的点

在q数组中的是当前凸包的位置，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+15;
ll a1,x,y,z,m;
ll n,L;
ll a[maxn];
ll sum[maxn];
int q[maxn];
double slope(int u,int v)
{
    return (double)(sum[u]-sum[v])/(u-v);
}
void create()
{
    scanf("%lld%lld",&n,&L);
    scanf("%lld%lld%lld%lld%lld",&a1,&x,&y,&z,&m);
    a[1]=a1;
    for(int i=2;i<=n;i++)
    {
        a[i]=((x*a[i-1]%m*a[i-1]%m+y*a[i-2]%m+z)%m+m)%m-m/2;
    }
//    for(int i=1;i<=n;i++)
//    {
//        printf("%lld ",a[i]);
//    }
}
void solve()
{
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+a[i];//前缀和  平均数  类似斜率
    }
    double ans=-1e12;
    int head=0,tail=1;
    q[head]=0;
    for(int i=L;i<=n;i++)
    {
        while(head+1<tail&&slope(q[head],q[head+1])<slope(q[head]+1,i))//保证满足凸包性质
            head++;
        ans=max(ans,slope(q[head],i));
        int in=i-L+1;//保证最短长度L
        while(head+1<tail&&slope(q[tail-1],q[tail-2])>slope(q[tail-1],in))//得到以L为最小距离的凸包
            tail--;
        q[tail]=in;
        tail++;
    }
    printf("%.10f",ans);
}

int main()
{
    create();
    solve();
    return 0;
}