首页 > 代码库 > Subsequence（hdu3530）
Subsequence（hdu3530）
Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6141 Accepted Submission(s): 2041
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
思路：优先队列+尺取；
我们不用去管这个子串中的最大最小的距离是否大于等于m，我们只要保证这个值小于等于k时继续向右端扩展，应为向右端扩展尺取时，当前值是越来越大的。比如当[l,r]满足dis>=m，那么[l,r+s],的dis>=m;所以我们不需要管m。然后就是尺取中，更新最大最小值的问题，这个用优先队列维护下。复杂度N*log(N);
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<stdlib.h> 6 #include<queue> 7 #include<stack> 8 using namespace std; 9 typedef long long LL; 10 int ask[100005]; 11 int cnt[100005]; 12 struct node1 13 { 14 int x; 15 int id; 16 bool operator<(const node1 &cx)const 17 { 18 if(cx.x == x) 19 return cx.id<id; 20 else return cx.x>x; 21 } 22 }; 23 struct node2 24 { 25 int x; 26 int id; 27 bool operator<(const node2 &cx)const 28 { 29 if(cx.x == x) 30 return cx.id<id; 31 else return cx.x<x; 32 } 33 }; 34 priority_queue<node1>que1; 35 priority_queue<node2>que2; 36 int main(void) 37 { 38 int n,m,k; 39 while(scanf("%d %d %d",&n,&m,&k)!=EOF) 40 { 41 while(!que1.empty())que1.pop(); 42 while(!que2.empty())que2.pop(); 43 int i,j; 44 for(i = 0; i < n; i++) 45 { 46 scanf("%d",&ask[i]); 47 } 48 int l = 0; 49 int r = 0; 50 int cc = 0; 51 int ma = ask[0]; 52 int mi = ask[0]; 53 int x = abs(ma-mi); 54 if(x <= k&&x >= m)cc = 1; 55 node1 ak; 56 node2 ap; 57 ak.x =ask[0]; 58 ak.id = 0; 59 ap.x = ask[0]; 60 ap.id = 0; 61 que1.push(ak); 62 que2.push(ap); 63 while(l<=r&&r<n) 64 { 65 while(x <= k &&r < n-1) 66 { 67 r++; 68 int c = abs(ask[r]-ma); 69 c = max(abs(ask[r]-mi),c); 70 if(c > k) 71 { //printf("%d %d\n",l,r); 72 r--; 73 break; 74 } 75 node1 ac; 76 ac.x = ask[r]; 77 ac.id = r; 78 node2 bc; 79 bc.x= ask[r]; 80 bc.id = r; 81 que1.push(ac); 82 que2.push(bc); 83 if(ask[r] > ma) 84 { 85 ma = ask[r]; 86 } 87 else if(ask[r] < mi) 88 { 89 mi = ask[r]; 90 } 91 x = abs(ma-mi);//printf("%d\n",x); 92 } 93 if(x >= m) 94 { 95 cc = max(cc,r-l+1); 96 } 97 if(ask[l] == ma) 98 { 99 while(!que1.empty())100 {101 node1 acc = que1.top();102 if(acc.id <= l)103 {104 que1.pop();105 }106 else107 {108 ma = acc.x;109 break;110 }111 }112 }113 if(ask[l]==mi)114 {115 while(!que2.empty())116 {117 node2 acc = que2.top();118 if(acc.id <= l)119 {120 que2.pop();121 }122 else123 {124 mi = acc.x;125 break;126 }127 }128 }129 l++;130 if(l == r+1)131 { //printf("%d\n",r);132 r++;133 node1 akk;134 node2 app;135 akk.x =ask[r];136 akk.id = r;137 app.x = ask[r];138 app.id = r;139 que1.push(akk);140 que2.push(app);141 mi = ask[r];142 ma = ask[r];143 }144 }145 printf("%d\n",cc);146 }147 return 0;148 }
Subsequence（hdu3530）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。