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.

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

释意：

　　第一行给出三个数n、m、k，第二行给出一个n个数序列，要求找出一个最长的连续子序列，要求子序列的最大值与最小值的差值要小于等于k大于等于m。

　　输出满足该条件的最长子序列的长度。 

题解：

　　由于要求最大值与最小值，所以建立两个单调队列，一个单调递增队列，一个单调递减队列，从而通过队头确定当前子序列的最大值与最小值，我们可以仅以

最大值-最小值 是否大于k来确定满足的当前序列的子序列，至于是否满足大于等于买这个条件，可以在比较时来确定是否加入比较的行列。

　　对于如何确定当前序列的满足条件的最长子序列问题：

1.求两队对头的差值，若小于等于k则满足。如不满足则将两队中队头元素下标较小的一个出队，用last1，last2分别几下当前队头元素的前一个元素的坐标，继续进行队头元素的比较。最终用 当前元素下标 i-max（last1，last2）便是满足条件的最长子序列的长度。

代码实现：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<string.h>
 5 using namespace std;
 6 struct Node
 7 {
 8     int value;
 9     int position;
10 }q1[100050],q2[100050]; // q1模拟单调递减队列，q2单调递增队列
11 int a[100050];
12 int main()
13 {
14     int n,m,k;
15     while(~scanf("%d %d %d",&n,&m,&k))
16     {
17         int head1 = 1, head2 = 1;
18         int tail1 = 0, tail2 = 0;
19         int last1 = 0, last2 = 0;
20         int ans = 0;  // 一定要初始化为0！！！！！！！
21         for(int i = 1;i<=n;i++) scanf("%d",a+i);
22         for(int i = 1;i<=n;i++)
23         {
24             while(head1<=tail1&&q1[tail1].value<=a[i]) tail1--;  //当前元素进队
25             q1[++tail1].position = i;
26             q1[tail1].value = a[i];
27 
28             while(head2<=tail2&&q2[tail2].value>=a[i]) tail2--; //当前元素进队
29             q2[++tail2].position = i;
30             q2[tail2].value = a[i];
31             
32             //确定当前序列的最长满足条件的子序列
33             
34             while(head1<=tail1&&head2<=tail2&&q1[head1].value-q2[head2].value>k)
35             {
36                 if(q1[head1].position<q2[head2].position)
37                 {
38                     last1 = q1[head1++].position;
39                 }
40                 else last2 = q2[head2++].position;
41             }
42 
43             if(q1[head1].value-q2[head2].value>=m)
44             ans = max(ans , i-max(last1,last2));  //  细细理解
45         }
46         cout<<ans<<endl;
47     }
48     return 0;
49 }

本文为个人随笔,如有不当之处,望各位大佬多多指教.
若能为各位博友提供小小帮助,不胜荣幸.

HDU 3530 --- Subsequence 单调队列

相关推荐