Subsequence-蒲公英云

Subsequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5092 Accepted Submission(s): 1691

Problem Description

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

Input

There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

Output

For each test case, print the length of the subsequence on a single line.

Sample Input

Sample Output

5
4

Source

2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int a[100005];
int main()
{
    int n,m,k,i,now,ans;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
        deque<int>q;
        q.clear();
        deque<int>Q;
        Q.clear();
        now=1,ans=0;
        for(i=1;i<=n;i++)
        {
            while(!q.empty()&&a[i]<a[q.back()])//单调递增序列
            q.pop_back();
            q.push_back(i);
            while(!Q.empty()&&a[i]>a[Q.back()])//单调递减序列
            Q.pop_back();
            Q.push_back(i);
            while(!q.empty()&&!Q.empty()&&a[Q.front()]-a[q.front()]>k)
            {
                if(q.front()<Q.front())
                {
                    now=q.front()+1;
                    q.pop_front();
                }
                else
                {
                    now=Q.front()+1;
                    Q.pop_front();
                }
            }
            if(a[Q.front()]-a[q.front()]>=m)
            {
                if(ans<i-now+1)
                ans=i-now+1;
            //    cout<<"ans= "<<ans<<endl;
            }
            /*
                这一题用两个队列维护区间
                一个单调递增序列一个单调递减序列
                两个头的值相减就是区间的范围
                所以每次插入一个值的时候必须让这个值遵循规则
                now只能在数列元素加一的时候才能动！
            */
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
8 2 6
1 3 8 5 2 7 5 2
*/