LuoguP1419 寻找段落（二分单调队列

题目描述

给定一个长度为n的序列a_i,定义a[i]为第i个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在[S,T]之间的连续序列。最有价值段落是指平均值最大的段落，

段落的平均值=段落总价值/段落长度。

输入输出格式

输入格式：

第一行一个整数n，表示序列长度。

第二行两个整数S和T，表示段落长度的范围，在[S,T]之间。

第三行到第n+2行，每行一个整数表示每个元素的价值指数。

输出格式：

一个实数，保留3位小数，表示最优段落的平均值。

输入输出样例

输入样例#1：

输出样例#1：

1.000

说明

【数据范围】

对于30%的数据有n<=1000。

对于100%的数据有n<=100000,1<=S<=T<=n，-10000<=价值指数<=10000。

【题目来源】

tinylic改编

题解

首先平均值这么麻烦的东西，当然是要先二分一下平均值然后一起减掉就可以变成判正负了2333

所以先二分一下最优段落的平均值，把每一项都减掉平均值，再求个前缀和．

然后设$i$为所选区间的右边界，那么$ans=s[i]-max_{j=i-t}^{s}s[j]$．

当$i$从小到大扫的时候，$j$的取值范围是单调右移的，转化为滑动窗口问题．

用一个单调队列从小到大维护$s[j]$就好了．

  qwerta

 P1419 寻找段落 Accepted

 代码 C++，.91KB

 提交时间 -- ::

 耗时/内存 510ms, 2228KB

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 inline int read()

 {

     char ch=getchar();

     int x=;bool s=;

     while(!isdigit(ch)){if(ch=='-')s=;ch=getchar();}

     while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

     return s?x:-x;

 }

 #define R register

 int n,S,T;

 int a[];

 double s[];

 double q[];

 int pos[];

 void erfen(double l,double r)

 {

     if(l+0.00001>r){printf("%.3f",l);exit();}

     double mid=0.5*(l+r);

     for(int i=;i<=n;++i)

     s[i]=s[i-]+(a[i]-mid);

     int he=,ta=;

     double ans=-1e9;

     for(int i=S;i<=n;++i)

     {

         if(pos[he]<i-T)he++;

         while(q[ta]>=s[i-S]&&ta>=he)ta--;

         q[++ta]=s[i-S];

         pos[ta]=i-S;

         ans=max(ans,s[i]-q[he]);

     }

     //cout<<l<<" "<<r<<" "<<mid<<" "<<ans<<endl;

     if(ans<)erfen(l,mid);

     else erfen(mid,r);

     return;

 }

 int main()

 {

     //freopen("a.in","r",stdin);

     n=read(),S=read(),T=read();

     for(R int i=;i<=n;++i)

     a[i]=read();

     erfen(-1e4-,1e4+);

 }

段落