hdu 3276

Problem from:http://acm.hdu.edu.cn/showproblem.php?pid=3276

在一个数列中寻找两个不相交且不相邻长度为Len(x<=Len<=y)的连续子序列,使这两个子数列的平均数最大，求该最大平均数

最大平均数用二分搜索来求

每次二分搜索一个值k，判断是否存在这样的两个子序列的平均值大于等于k，存在则向上二分搜索，不存在则向下搜索

如何判断一个数列的平均值与k的大小关系：把每个数减去k,再求所有数的和(此处的和假设用Ek表示)

DP在该处的运用：DP[i]用来存储数列前 i 个数中，所有长度为Len(x<=Len<=y)的连续子序列中最大的Ek(Ek:上一行有定义)

剩下的我们就只要枚举原数列下标i(x<i,i+x<=n)

判断第1..到..第i-1的数列中满足长度子序列最大的Ek 与第i+1..到..第n的数列中满足长度子序列最大的Ek 的和是否>=0

最后剩下的就是如何实现DP了：

DP前，先用一个数组sum[]，sum[i]存前 i 个数的 Ek

假设DP[i-1]已实现，则DP[i]=max(DP[i-1] , max(sum[i]-sum[j] (x<= i-j <=y) ) )

这时用的技巧就是用双端队列快速求 max(sum[i]-sum[j] (x<= i-j <=y) )//i-y<= j <=i-x

每次求DP[i]时，向双端队列末端加入sum[]下标i-x

在向双端队列末端加入sum[]下标i-x 前，判断双端队列末端的元素s,sum[s]是否>sum[i-x],是则弹出该s,直到队列为空或者不存在sum[s]>s[i-x] 再加入i-x

然后判断双端队列首端的元素s，s是否<i-y,是则弹出该s,直到队列中不存在<i-y的s

这样的操作可以保证双端队列中的元素s全部满足（i-y<=s<=i-x）且从首端到末端的sum[s]是呈递增的

此时就可以判定DP[i]=max(DP[i-1],sum[i]-sum[s](s为双端队列首端的元素))

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=50010;
int a[MAXN],n,x,y,Case;
double sum[MAXN],Ldp[MAXN],Rdp[MAXN];//sum[i]存前i个数的Ek；Ldp[i]存前i个数中 满足长度的子序列 中的最大Ek；Rdp[i]存第i个数到第n个个数中 满足长度的子序列 中的最大Ek
bool f(double dt){
    sum[0]=0;
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-dt;
    deque<int> que;
    Ldp[x-1]=-1e10;
    for(int i=x;i<n-x;i++){//求Ldp[]
        while(!que.empty() && sum[i-x]<sum[que.back()])
            que.pop_back();
        que.push_back(i-x);
        while(que.front()<i-y)
            que.pop_front();
        Ldp[i]=max(Ldp[i-1],sum[i]-sum[que.front()]);
    }
    que.clear();
    sum[n+1]=0;
    for(int i=n;i>0;i--)sum[i]=sum[i+1]+a[i]-dt;
    Rdp[n-x+2]=-1e10;
    for(int i=n-x+1;i>x;i--){//求Rdp[]，原理和求Ldp[]一样
        while(!que.empty() && sum[i+x]<sum[que.back()])
            que.pop_back();
        que.push_back(i+x);
        while(que.front()>i+y)
            que.pop_front();
        Rdp[i]=max(Rdp[i+1],sum[i]-sum[que.front()]);
    }
    for(int i=x+1;i<=n-x;i++)//枚举判断
        if(Ldp[i-1]+Rdp[i+1]>=0)return true;
    return false;
}
void work(){
    double L=1,R=200000,ans;
    while(R-L>1e-5){
        ans=(L+R)/2;//二分搜索最大平均值
        if(f(ans))L=ans;
        else R=ans;
    }
    printf("Case %d: %.3lf
",++Case,ans);
}
int main()
{
    while(scanf("%d%d%d",&n,&x,&y)!=EOF){
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        work();
    }
    return 0;
}

View Code

后来，我用优先队列(编码会简单些)来实现，时间复杂度还是高了点，超时。

双端队列和队列一样是可以用数组来实现的，尤其是像这样的每个元素最多入队一次出队一次的题，实现起来没压力