【hdu3530】Subsequence

2015.03.15 22:57 Sun | 11次阅读 | 旧日oi | 固定链接 | 源码

题目大意: 给定一个数列,长度n(1<=n<=100000), 值m和k, 求最长子序列,满足当中的最大值-最小值差不小于m且不大于k。
题解
单调队列三连击!
同时维护两个队列,一个最大,一个最小,当新加入元素后,如果最大-最小>k.就得把之前的起点(两个队列队头的较小值)+1,并删除起点较小的队列的队头。否则如果最大-最小在m,k之间,可以更新答案,如果小于m,忽略不计就行。

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 100100
using namespace std;
struct node{
    int num;
    int pos;
}qmax[maxn],qmin[maxn],temp;
int n,m,k,st,ans;
int tmax,tmin,fmax1,fmin1;
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        ans=st=0;tmax=-1,tmin=-1,fmax1=0,fmin1=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&temp.num);temp.pos=i;
            while(fmax1<=tmax&&qmax[tmax].num<=temp.num) tmax--;
            qmax[++tmax]=temp;
            while(fmin1<=tmin&&qmin[tmin].num>=temp.num) tmin--;
            qmin[++tmin]=temp;
            while(qmax[fmax1].num-qmin[fmin1].num>k)
            {
                if(qmax[fmax1].pos<qmin[fmin1].pos)
                {
                    st=qmax[fmax1].pos+1;
                    fmax1++;
                }
                else
                {
                    st=qmin[fmin1].pos+1;
                    fmin1++;
                }
            }
            if(qmax[fmax1].num-qmin[fmin1].num>=m&&qmax[fmax1].num-qmin[fmin1].num<=k) 
            ans=max(ans,i-st+1);
        }
        printf("%d\n",ans);
    }
    return 0;
}```