Subsequence http://acm.hdu.edu.cn/showproblem.php?pid=3530
题意:
给出一个序列, 要求从中找到一个最长子区间, 满足 m=< 最大值 - 最小值 <=k, 求最长子区间的长度是多少?
分析:
枚举这个最长子区间的右边界, 然后在这个基础上, 找到满足上述条件的最左可行区间, 考虑用两个单调队列维护区间最大值和最小值, 通过调节子区间的最大值和最小值, 找到左边界.
参考资料: 大佬博客 https://blog.csdn.net/u014355480/article/details/48207341
代码:
- #include <stack>
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define ll long long
- #define ull unsigned long long
- #define cls(x) memset(x,0,sizeof(x))
- #define clslow(x) memset(x,-1,sizeof(x))
- const int maxn=1e5+100;
- int n,m,k,ans;
- int a[maxn];
- int que1[maxn],que2[maxn];
- void solve()
- {
- //pos 记录可行区间的左边界
- int pos=1;
- int head1=0,rear1=0,head2=0,rear2=0;
- for(int i=1;i<=n;i++){
- while(rear1>head1&&a[que1[rear1-1]]>a[i]) rear1--;
- while(rear2>head2&&a[que2[rear2-1]]<a[i]) rear2--;
- // 单调递增区间, 维护最小值
- que1[rear1++]=i;
- // 单调递减区间, 维护最大值
- que2[rear2++]=i;
- // 找到最左可行区间
- while(rear1>head1&&rear2>head2&&a[que2[head2]]-a[que1[head1]]>k){
- // 跳出循环时, pos 不会被赋值, 所以需要在循环里 + 1
- if(que2[head2]>que1[head1]) pos=que1[head1++]+1;
- else pos=que2[head2++]+1;
- }
- if(rear1>head1&&rear2>head2&&a[que2[head2]]-a[que1[head1]]>=m){
- ans=max(ans,i-pos+1);
- }
- }
- }
- int main()
- {
- // freopen("in.txt","r",stdin);
- while(scanf("%d%d%d",&n,&m,&k)!=EOF)
- {
- ans=0;
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- }
- solve();
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2703830.html