首页 > 代码库 > HDU - 3530 - Subsequence
HDU - 3530 - Subsequence
先上题目：
Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4100 Accepted Submission(s): 1341
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
题意：给出一个数字序列，求出最长的那一段数，这段数的最大值和最小值的差在给定的两个值之间，求出最长的长度。
这一题用到了单调队列，两个单调队列，一个用来保存前方单调最小值的下标，一个用来保存前方单调最大值的下标。当前段的最值之差大于限定值的时候就去除当前段的最前面的那个数，如果差值在小的限定值之下，就不用管它，如果在限定值之间就判断是不是最长的。
上代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <algorithm> 5 #define MAX 100002 6 using namespace std; 7 8 int a[MAX]; 9 10 deque<int> maxn,minn;11 12 int main()13 {14 int n,m,k,f,ans;15 // freopen("data.txt","r",stdin);16 while(scanf("%d %d %d",&n,&k,&m)!=EOF){17 while(!maxn.empty()) maxn.pop_front();18 while(!minn.empty()) minn.pop_front();19 for(int i=0;i<n;i++) scanf("%d",&a[i]);20 ans=0;21 f=0;22 for(int i=0;i<n;i++){23 while(!maxn.empty() && a[maxn.back()]<a[i]) maxn.pop_back();24 while(!minn.empty() && a[minn.back()]>a[i]) minn.pop_back();25 maxn.push_back(i);26 minn.push_back(i);27 while(!maxn.empty() && !minn.empty() && (a[maxn.front()]-a[minn.front()])>m){28 if(maxn.front() > minn.front()){29 f = minn.front();30 minn.pop_front();31 }else if(minn.front() > maxn.front()){32 f = maxn.front();33 maxn.pop_front();34 }else{35 f = maxn.front();36 maxn.pop_front();37 minn.pop_front();38 }39 f++;40 }41 if(!maxn.empty() && !minn.empty() && (a[maxn.front()] - a[minn.front()])>=k){42 ans = max(i-f+1,ans);43 }44 }45 printf("%d\n",ans);46 }47 return 0;48 }
HDU - 3530 - Subsequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。