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]$就好了．

 1  qwerta 
 2 P1419 寻找段落 Accepted 
 3 100
 4 代码 C++，0.91KB
 5 提交时间 2018-10-26 11:17:34
 6 耗时/内存 510ms, 2228KB
 7 #include<iostream>
 8 #include<cstdlib>
 9 #include<cstdio>
10 #include<cmath>
11 using namespace std;
12 inline int read()
13 {
14     char ch=getchar();
15     int x=0;bool s=1;
16     while(!isdigit(ch)){if(ch=='-')s=0;ch=getchar();}
17     while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
18     return s?x:-x;
19 }
20 #define R register
21 int n,S,T;
22 int a[100003];
23 double s[100003];
24 double q[100003];
25 int pos[100003];
26 void erfen(double l,double r)
27 {
28     if(l+0.00001>r){printf("%.3f",l);exit(0);}
29     double mid=0.5*(l+r);
30     for(int i=1;i<=n;++i)
31     s[i]=s[i-1]+(a[i]-mid);
32     int he=1,ta=0;
33     double ans=-1e9;
34     for(int i=S;i<=n;++i)
35     {
36         if(pos[he]<i-T)he++;
37         while(q[ta]>=s[i-S]&&ta>=he)ta--;
38         q[++ta]=s[i-S];
39         pos[ta]=i-S;
40         ans=max(ans,s[i]-q[he]);
41     }
42     //cout<<l<<" "<<r<<" "<<mid<<" "<<ans<<endl;
43     if(ans<0)erfen(l,mid);
44     else erfen(mid,r);
45     return;
46 }
47 int main()
48 {
49     //freopen("a.in","r",stdin);
50     n=read(),S=read(),T=read();
51     for(R int i=1;i<=n;++i)
52     a[i]=read();
53     erfen(-1e4-3,1e4+3);
54 }