Subsequence
发布时间:2020-12-15 07:52:35 所属栏目:Java 来源:网络整理
导读:Subsequence Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10796????Accepted Submission(s): 3613 Problem Description There is a sequence of integers. Your task is to find the longes
SubsequenceTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
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
#pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; const int maxn=1e5+108; typedef long long ll; int n,m,k; int c[maxn]; int max_queue[maxn],min_queue[maxn]; int main() { #ifndef ONLINE_JUDGE freopen("1.txt","r",stdin); #endif while(scanf("%d%d%d",&n,&m,&k)!=EOF){ int max_head=1,max_tail=0,min_head=1,min_tail=0,res=0; int f=0; for(register int i=1;i<=n;++i){ scanf("%d",&c[i]); while(max_head<=max_tail&&c[i]>=c[max_queue[max_tail]])max_tail--; while(min_head<=min_tail&&c[i]<=c[min_queue[min_tail]])min_tail--; max_queue[++max_tail]=i; min_queue[++min_tail]=i; while(c[max_queue[max_head]]-c[min_queue[min_head]]>k){ f=min(min_queue[min_head],max_queue[max_head]); if(f==min_queue[min_head]){ ++min_head; } if(f==max_queue[max_head]){ ++max_head; } } if(c[max_queue[max_head]]-c[min_queue[min_head]]>=m)res=max(res,i-f); } printf("%dn",res); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- java – UTF-8和UTF-16之间是否存在巨大差异
- 详解SpringMVC注解版前台向后台传值的两种方式
- java-ee – 在两个节点上导致相同弹性搜索查询的不同搜索结
- 程序集 – 返回中断处理程序后程序计数器的位置?
- Spring注解@RestControllerAdvice原理解析
- How to Read, Write XLSX File in Java - Apach POI Exampl
- java实现字符串转String数组的方法示例
- java组件fileupload文件上传demo
- java – 在同一实体上JOIN FETCH之后的Hibernate额外查询
- java – Android studio dalvik vm找不到类