1.题目描述：

Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6671    Accepted Submission(s): 2238 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   Source 2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU   Recommend zhengfeng   |   We have carefully selected several similar problems for you:   3535  3529  3528  3527  3531 

2.题意概述：

给出一个大小为n的数组a[n];

求其中最大值减最小值在[m,k]区间中的字串最长长度。

3.解题思路：

同样可以考虑在从左扫描的同时用单调栈维护当前最值，如果最值超过了就去掉队列前面的元素，至于是去最大值还是最小值应该贪心地去掉下标最小的那个元素。

去除得到合法解，如果区间值符合，就更新一下最值，注意初始化ans应该是0！

4.AC代码：

#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <functional> #include <cmath> #include <vector> #include <queue> #include <deque> #include <stack> #include <map> #include <set> #include <ctime> #define INF 0x3f3f3f3f #define maxn 100100 #define lson root << 1 #define rson root << 1 | 1 #define lent (t[root].r - t[root].l + 1) #define lenl (t[lson].r - t[lson].l + 1) #define lenr (t[rson].r - t[rson].l + 1) #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; int a[maxn], qmin[maxn], qmax[maxn]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif int n, m, k; while (~scanf("%d%d%d", &n, &m, &k)) { int ans = 0, head1 = 0, head2 = 0, tail1 = 0, tail2 = 0, pre = 0; a[0] = qmax[0] = qmin[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); //维护单调递减 while (head1 <= tail1 && a[qmin[tail1]] > a[i]) tail1--; //维护单调递增 while (head2 <= tail2 && a[qmax[tail2]] < a[i]) tail2--; qmin[++tail1] = i; qmax[++tail2] = i; while (a[qmax[head2]] - a[qmin[head1]] > k) pre = qmin[head1] < qmax[head2] ? qmin[head1++] : qmax[head2++]; if (a[qmax[head2]] - a[qmin[head1]] >= m && a[qmax[head2]] - a[qmin[head1]] <= k) ans = max(ans, i - pre); } printf("%d\n", ans); } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }