首页 > 代码库 > HDU - 3530 Subsequence
HDU - 3530 Subsequence
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
2010 ACM-ICPC Multi-University Training Contest(10)――Host by HEU
题意:求一个最长的最大和最小的差在[m, k]范围的序列
思路:维护一个最大序列和一个最小序列,然后判断是否符合范围就行了
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <queue> using namespace std; const int maxn = 100010; int num[maxn]; int q1[maxn], q2[maxn]; int n, m, k; int main() { while (scanf("%d%d%d", &n, &m, &k) != EOF) { for (int i = 1; i <= n; i++) scanf("%d", &num[i]); int ans = 0; int rear1 = 0, front1 = 0, rear2 = 0, front2 = 0; int cnt = 0; for (int i = 1; i <= n; i++) { while (front1 < rear1 && num[q1[rear1-1]] < num[i]) rear1--; q1[rear1++] = i; while (front2 < rear2 && num[q2[rear2-1]] > num[i]) rear2--; q2[rear2++] = i; while (front1 < rear1 && front2 < rear2 && num[q1[front1]]-num[q2[front2]] > k) { if (q1[front1] < q2[front2]) { cnt = q1[front1]; front1++; }else { cnt = q2[front2]; front2++; } } if (front1 < rear1 && front2 < rear2 && num[q1[front1]]-num[q2[front2]] >= m) ans = max(ans, i-cnt); } printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。