luoguP1419 寻找段落(二分答案+单调队列）

题意

给定一个长度为n的序列a₁~a_n，从中选取一段长度在s到t之间的连续一段使其平均值最大。（n<=100000)

题解

二分答案平均值。

judge时把每一个a[i]-mid得到b[i]

在b[i]中找到一段合法的串使其权值和最大。

当最大权值和大于等于0时则mid上移。

求最大权值和用单调队列就行。（预处理b[i]的前缀和sum[i]，队列中记录当前位置可选区间的最小的sum[i]）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #define maxn 200010
 5 using namespace std;
 6 int n, s, t, i;
 7 double l, r, mid, ans;
 8 double a[maxn];
 9 int b[maxn];
10 double sum[maxn];
11 int q[maxn];
12 bool check(double x) {
13     int i,l=1,r=0;
14     for(i=1;i<=n;i++)
15         a[i]=(double)b[i]-x;
16     sum[0]=0;
17     for(i=1;i<=n;i++)
18         sum[i]=sum[i-1]+a[i];
19     for(i=1;i<=n;i++) {
20         if(i>=s){
21             while(r>=l&&sum[i-s]<sum[q[r]])r--;
22             q[++r]=i-s;
23         }
24         if(l<=r&&q[l]<i-t)l++;
25         if(l<=r&&sum[i]-sum[q[l]]>=0)return true;
26     }
27     return false;
28 }
29 int main() {
30  // freopen("seq.in","r",stdin);
31 //  freopen("seq.out","w",stdout);
32     scanf("%d",&n);
33     scanf("%d%d",&s,&t);
34     for (i=1;i<=n;i++)
35         scanf("%d",&b[i]);
36     ans=l=-10000;r=10000;
37     while(r-l>1e-5) {
38         mid=(l+r)/2;
39         if(check(mid))
40             ans=l=mid;
41         else r=mid;
42     }
43     printf("%.3lf
", ans);
44     return 0;
45 }