寻找段落

发表于 更新于 分类于 阅读次数：

Luogu P1419 寻找段落 题意：要求找出长度在S到T之间段落最大平均值 首先本题可以二分答案转化为判定性问题 如果一个区间有$k$个元素，和为$sum$，平均值$\ge x$ $sum/k \ge x$ $sum-k \times x \ge 0$ 将每一个值都减去$x$，求出$sum$得到$sum \ge 0$ 求出序列每个元素减去$x$后的前缀和 只要知道$i-T$到$i-S$间的最小值，即可求得区间内最大平均值，可使用单调队列维护 如果区间内$i < j < k$，$pre_i>pre_j$，则$pre_k-pre_j>pre_k-pre_i$，$pre_i$已不是最优答案，可以出队 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

int read()
{
    int a=1,b=0; char c;
    do{c=getchar(); if(c=='-') a=-1;}while(c<'0'c>'9');
    do{b=b*10+c-'0'; c=getchar();}while(c>='0'&&c<='9');
    return a*b;
}

const int MAXN=100000+100;
int num[MAXN];

int N,S,T;
double lft,rigt,ans,mid;
double pre_sum[MAXN];
std::deque<int> que;

bool judge(double x)
{
    que.clear();
    for(int i=1;i<=N;++i){
        pre_sum[i]=pre_sum[i-1]+(double)num[i]-x;
    }
    for(int i=1;i<=N;++i){
        if(i>=S){
            while(!que.empty() && pre_sum[que.front()]>pre_sum[i-S])
                que.pop_front();
            que.push_back(i-S);
        }
        if(!que.empty() && que.front()<i-T)
            que.pop_front();
        if(!que.empty() && pre_sum[i]-pre_sum[que.front()]>=0)
            return true;
    }
    return false;
}

int main()
{
    N=read(); S=read(); T=read();
    for(int i=1;i<=N;++i) num[i]=read();
    lft=-10000.0; rigt=10000.0;
    while(rigt-lft>=1e-5){
        mid=(rigt+lft)/2;
        if(judge(mid))
            lft=ans=mid;
        else rigt=mid;
    }
    printf("%.3f\n",ans);
    return 0;
}