题解 P1419 【寻找段落】

· · 题解

前言

鉴于这题的题解质量（连LaTeX公式都没有），我决定再发一篇详细的题解，不仅方便大家，还可以作为我学习单调队列优化dp的小结（尽管这题不是dp）。

分析

题目要求求一个最大的实数x，使得某长度在[S,T]之间的区间[L,R]满足

\frac{\sum_{i=L}^{R}a_i}{R-L+1}=x

即

\sum_{i=L}^{R}a_i=x*(R-L+1)

由于答案满足单调性，所以可以二分x，转化为判断问题，即判断

\sum_{i=L}^{R}a_i\geq x*(R-L+1) \rightarrow \sum_{i=L}^{R}\left(a_i-x \right)\geq0

对这个式子求前缀和，就可快速算出一段区间的和，令

sum_i=\sum_{i=1}^{i}\left(a_i-x \right)

则区间[L,R]合法的条件为

sum_R-sum_{L-1}\geq0

转化成这种形式，已经很好做了。维护一个单增的单调队列，然后判断当前遍历元素是否大于等于队首元素即可。

时间复杂度

假设数据范围为A，则二分答案是O(\log A)的，判断一次用了前缀和和单调队列，是O(n)的，总时间复杂度为O(n\log A)。

小优化

题目要求保留3位小数，而对浮点数的操作很麻烦，所以不妨对每个数乘10000（多一位是因为要四舍五入），然后算答案时再除10000.0就行了。

代码

用STL的deque实现单调队列，嫌慢手打，使用相同API即可（然而这题不卡可以水^_^）。

#include<iostream>
#include<cstdio>
#include<deque>
#include<cstring>
#define rg register
template<typename T>inline T read(T&x)
{
    T data=0;
    int w=1;
    char ch=getchar();
    while(ch!='-'&&!isdigit(ch))
        ch=getchar();
    if(ch=='-')
        w=-1,ch=getchar();
    while(isdigit(ch))
        data=data*10+ch-'0',ch=getchar();
    return x=data*w;
}
using namespace std;
typedef long long ll;

const int MAXN=1e5+7;
int n,S,T;
int a[MAXN];
ll sum[MAXN]; // prefix sum
int L=1e8,R=-1e8;

deque <int> Q;

inline bool judge(int x)
{
//  cerr<<"judging x="<<x<<endl;
    memset(sum,0,sizeof(sum));
    for(rg int i=1;i<=n;++i)
    {
        sum[i]=sum[i-1]+a[i]-x;
//      clog<<"sum["<<i<<"]= "<<sum[i]<<endl;
    }
    Q.clear();
    for(rg int i=S,p=0;i<=n;++i,++p)
    { // 只有一段不包括本身的区间内合法，就开两个扫描线
        while(!Q.empty()&&sum[Q.back()]>sum[p])
            Q.pop_back();
        Q.push_back(p);
        while(Q.front()<i-T) // 这里不用判空是因为p一定存在
            Q.pop_front();
        if(sum[i]-sum[Q.front()]>=0)
            return 1;
    }
//  cerr<<"failed"<<endl;
    return 0;
}

int main()
{
    read(n);read(S);read(T);
    for(rg int i=1;i<=n;++i)
    {
        read(a[i]);
        a[i]*=1e4;
//      cerr<<"a["<<i<<"]= "<<a[i]<<endl;
        L=min(L,a[i]);
        R=max(R,a[i]);
    }
    while(L<R)
    {
        int M=(L+R+1)>>1;
        if(judge(M))
            L=M;
        else
            R=M-1;
    }
    printf("%.3f",L/1e4);
}

Hint

最后说一下单调队列的边界问题。合法区间[L,R]满足

S\leq R-L+1\leq T

由于使用前缀和，那么i，p应满足

S+1\leq i-p+1\leq T+1

也就是说应弹掉p<i-T的那些点。

还有就是二分答案的边界。求最后一个类型应该int M=(L+R+1)>>1;