描述:
Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6143 Accepted Submission(s): 2042
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.
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
Recommend
题意:
给你一个长度为n的数列,求最长子区间的长度,使得区间的最大值与最小值的差s满足,
m<=s<=k
思路:
这题很容易想到用两个单调队列维护当前最值,
作为判断条件,如果差值大于k了,就去掉较前面的那个队列元素,并把区间头更新为它的标号+1,
这里注意差值小于m并不需要去掉元素,还有更新答案时要先判断是否满足条件才能更新。
代码:
#include <bits/stdc++.h> #define pr(x) cout << #x << "= " << x << " " ; #define pl(x) cout << #x << "= " << x << endl; #define ll __int64 using namespace std; template<class T> void read(T&num) { char CH; bool F=false; for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar()); for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar()); F && (num=-num); } int stk[70], tp; template<class T> inline void print(T p) { if(!p) { puts("0"); return; } while(p) stk[++ tp] = p%10, p/=10; while(tp) putchar(stk[tp--] + '0'); putchar('\n'); } const int N=1e5+10; int n,m,k,a[N]; int qmin[N],qmax[N]; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif while(~scanf("%d%d%d",&n,&m,&k)){ int lm=0,rm=0,lx=0,rx=0,ans=0,l=0; for(int i=1; i<=n; i++){ read(a[i]); while(lm<rm && a[qmin[rm-1]]>a[i])rm--;//递增 while(lx<rx && a[qmax[rx-1]]<a[i])rx--;//递减 qmin[rm++]=i; qmax[rx++]=i; while(a[qmax[lx]]-a[qmin[lm]]>k){ l=(qmin[lm]<qmax[lx])?qmin[lm++]:qmax[lx++]; } if(a[qmax[lx]]-a[qmin[lm]]>=m){ ans=max(ans, i-l);//因为l从0开始所以i-l不需要+1 } } print(ans); } return 0; }