Subsequence

一时失言乱红尘 2022-08-03 05:15 32阅读 0赞

# 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

5 0 0
    1 1 1 1 1
    5 0 3
    1 2 3 4 5

Sample Output

5
    4

Source

[2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU][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
    */

[2010 ACM-ICPC Multi-University Training Contest_10_Host by HEU]: http://acm.hdu.edu.cn/search.php?field=problem&key=2010+ACM-ICPC+Multi-University+Training+Contest%A3%A810%A3%A9%A1%AA%A1%AAHost+by+HEU&source=1&searchmode=source