HDU 3530 Subsequence

本文主要是介绍HDU 3530 Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题意是给你n个数，然后寻找一个区间，区间的最大值与最小值的差要小于k并且大于m

思路：

用两个单调序列维护这个序列，显而易见用当前者两个单调序列的列首相减如果大于k的话那么，我们就要寻找列首在序列位置比较小的那个往后面加1。这个题目的难点在于题目意思是区间，我理解错了。以为是那种最长公共子序列那种。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int last,head;
int n,m,k;
int a[111111];int que1[111111];
int que2[111111];
int pa[111111];
int pb[111111];int main(){while(scanf("%d%d%d",&n,&m,&k)!=EOF){for(int i=1;i<=n;i++){scanf("%d",&a[i]);}int l1=0;int l2 = 0;int ans = 0;int l = 0;int r1 = -1;int r2 = -1;for(int i=1;i<=n;i++){while(l1<=r1&&a[que1[r1]]>a[i]) --r1;while(l2<=r2&&a[que2[r2]]<a[i]) --r2;que1[++r1] = i;que2[++r2] = i;while(a[que2[l2]]-a[que1[l1]]>k){if(que1[l1]<que2[l2]) l = que1[l1++];else l = que2[l2++];}if(a[que2[l2]]-a[que1[l1]]>=m&&a[que2[l2]]-a[que1[l1]]<=k)ans = max(ans,i-l);}printf("%d\n",ans);}
}

这篇关于HDU 3530 Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---