http://acm.hdu.edu.cn/showproblem.php?pid=3530
题意:
找一个最长的区间,区间最大值与最小值的差 大于等于小于等于k
分析:
维护最大值与最小值,然后最大的最大值与最小的最小值的差是不是大于y,大于y谁在前面删除谁,记录起点。
代码如下:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> using namespace std; const int maxn = 100010; int a[maxn]; int main() { int n,m,k; while(~scanf("%d%d%d",&n,&m,&k)){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); deque<int > mmax; deque<int > mmin; int ans = 0; int st = 0; for(int i=1;i<=n;i++){ while(!mmax.empty()&&a[i]>a[mmax.back()]) mmax.pop_back();//维护单调性 while(!mmin.empty()&&a[i]<a[mmin.back()]) mmin.pop_back();//维护单调性 mmax.push_back(i); mmin.push_back(i); while(!mmax.empty()&&!mmin.empty()&&a[mmax.front()]-a[mmin.front()]>k){ if(mmax.front()<mmin.front()){ st = mmax.front(); mmax.pop_front(); } else { st=mmin.front(); mmin.pop_front(); } } if(!mmax.empty()&&!mmin.empty()&&a[mmax.front()]-a[mmin.front()]>=m) ans = max(ans,i-st); } cout<<ans<<endl; } return 0; }