HDU 3530 Subsequence 题解

HDU 3530 Subsequence 题解

HDU 3530

题目

$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$.

输入

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, print the length of the subsequence on a single line.

样例

input
5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5

output
5
4

题意

求一个最大值-最小值的差大于 $m$小于 $k$的子序列

解题思路

两个单调队列
一个递减求区间最大值
一个递增求区间最小值
最大值与最小值的差如果大于 $k$
就出队（它只会越来越大，对后面答案没有贡献）

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k,a[1000020],q[1000010],q2[1000020];
int main()
{while (scanf("%d%d%d",&n,&m,&k)!=EOF){for (int i=1;i<=n;i++)scanf("%d",&a[i]);int h=1,t=1,h1=1,t1=1,sum=1,ans=0;for (int i=1;i<=n;i++){while (h<t&&a[q[t-1]]<a[i]) t--;  //递减while (h1<t1&&a[q2[t1-1]]>a[i]) t1--;  //递增q[t++]=i;q2[t1++]=i;   //入队while (h<t&&h1<t1&&a[q[h]]-a[q2[h1]]>k)  //最大值与最小值的差超出范围if (q2[h1]>q[h])  //更新小的sum=q[h]+1,h++;else sum=q2[h1]+1,h1++;if (h<t&&h1<t1&&a[q[h]]-a[q2[h1]]>=m) //在范围以内  ans=max(ans,i-sum+1);   //更新答案}printf("%d\n",ans);}return 0;
}