首页 > 代码库 > bzoj2096[Poi2010]Pilots*
bzoj2096[Poi2010]Pilots*
bzoj2096[Poi2010]Pilots
题意：
给一个序列和一个最大值，要求找一个最长连续子串，使里面任意两个数相差不超过这个最大值。序列大小≤3000000
题解：
用两个单调队列，分别维护当前区间的最大值和最小值，然后用双指针法。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 3000010 6 using namespace std; 7 8 inline int read(){ 9 char ch=getchar(); int f=1,x=0;10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}11 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();12 return f*x;13 }14 struct nd{int v,pos;};15 int n,a[maxn],k,l,r,ans,ql1,qr1,ql2,qr2; nd q1[maxn],q2[maxn];16 int main(){17 k=read(); n=read(); inc(i,1,n)a[i]=read();18 l=1; r=1; ans=1; ql1=qr1=ql2=qr2=1; q1[1]=q2[1]=(nd){a[1],1};19 while(r<n){20 r++;21 while(ql1<=qr1&&ql2<=qr2&&a[r]-q1[ql1].v>k){l++; if(l>q1[ql1].pos)ql1++; if(l>q2[ql2].pos)ql2++;}22 while(ql1<=qr1&&ql2<=qr2&&q2[ql2].v-a[r]>k){l++; if(l>q1[ql1].pos)ql1++; if(l>q2[ql2].pos)ql2++;}23 ans=max(ans,r-l+1);24 while(ql1<=qr1&&a[r]<=q1[qr1].v)qr1--; q1[++qr1]=(nd){a[r],r};25 while(ql2<=qr2&&a[r]>=q2[qr2].v)qr2--; q2[++qr2]=(nd){a[r],r};26 }27 printf("%d",ans); return 0;28 }
20160829
bzoj2096[Poi2010]Pilots*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。