P3512 [POI2010]PIL-Pilots(单调队列+二分） 输入格式： 输出格式：
题目描述
In the Byteotian Training Centre, the pilots prepare for missions requiring extraordinary precision and control.
One measure of a pilot's capability is the duration he is able to fly along a desired route without deviating too much - simply put, whether he can fly steadily. This is not an easy task, as the simulator is so sensitive that it registers even a slightest move of the yoke1.
At each moment the simulator stores a single parameter describing the yoke's position.
Before each training session a certain tolerance level is set.
The pilots' task then is to fly as long as they can in such a way that all the yoke's position measured during the flight differ by at most . In other words, a fragment of the flight starting at time
and ending at time
is within tolerance level
if the position measurements, starting with
-th and ending with
-th, form such a sequence
that for all elements
of this sequence, the inequality
holds.
Your task is to write a program that, given a number and the sequence of yoke's position measurements, determines the length of the longest fragment of the flight that is within the tolerance level
.
给定n,k和一个长度为n的序列，求最长的最大值最小值相差不超过k的序列
输入输出格式
In the first line of the standard input two integers are given, and
(
,
), separated by a single space, denoting the tolerance level and the number of yoke's position measurements taken.
The second line gives those measurements, separated by single spaces. Each measurement is an integer from the interval from to
.
第一行两个有空格隔开的整数k（0<=k<=2000,000,000），n(1<=n<=3000,000)，k代表设定的最大值，n代表序列的长度。第二行为n个由空格隔开的整数ai（1<=ai<=2000,000,000），表示序列。
输出格式：
Your program should print a single integer to the standard output:
the maximum length of a fragment of the flight that is within the given tolerance level.
一个整数代表最大的符合条件的序列
输入输出样例
说明
样例解释：5, 8, 6, 6 和8, 6, 6, 9都是满足条件长度为4的序列
单调队列有顺序性
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define ll long long 5 ll k,n,a[3000005],q_mx[3000005],q_mn[3000005]; 6 ll head_mx,head_mn,tail_mx,tail_mn,len,pre; 7 int main(){ 8 // freopen("1.in","r",stdin); 9 scanf("%lld%lld",&k,&n); 10 len=0; 11 for(int i=1;i<=n;i++)scanf("%lld",&a[i]); 12 q_mx[1]=1;q_mn[1]=1;pre=1; 13 head_mx=1;tail_mx=1;head_mn=1;tail_mn=1; 14 for(int i=2;i<=n;i++){ 15 while(head_mx<=tail_mx&&a[q_mx[tail_mx]]<a[i])tail_mx--; 16 while(head_mn<=tail_mn&&a[q_mn[tail_mn]]>a[i])tail_mn--; 17 q_mx[++tail_mx]=i;q_mn[++tail_mn]=i; 18 while(a[q_mx[head_mx]]-a[q_mn[head_mn]]>k){ 19 if(q_mx[head_mx]<q_mn[head_mn]){pre=q_mx[head_mx]+1;head_mx++;} 20 else {pre=q_mn[head_mn]+1;head_mn++;} 21 } 22 //pre=min(q_mx[head_mx],q_mn[head_mn]); 23 len=max(len,i-pre+1); 24 } 25 printf("%lld",len); 26 }
二分：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<deque> 6 using namespace std; 7 const int MAXN=3000010; 8 inline void read(int &n) 9 { 10 char c=getchar();n=0;bool flag=0; 11 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar(); 12 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n; 13 } 14 struct node 15 { 16 int pos,val; 17 node(){pos=val=0;} 18 node(int a,int b) { pos=a;val=b; } 19 }; 20 int a[MAXN]; 21 int n,k; 22 int check(int mid)//按顺序的性质二分 23 { 24 deque<node>qmax;// 升 25 deque<node>qmin;// 降 26 for(int i=1;i<=n;i++) 27 { 28 while(qmax.size()>0&&qmax.front().pos<=(i-mid)) qmax.pop_front(); 29 while(qmin.size()>0&&qmin.front().pos<=(i-mid)) qmin.pop_front(); 30 while(qmax.size()>0&&a[i]>qmax.back().val) qmax.pop_back(); 31 qmax.push_back(node(i,a[i])); 32 while(qmin.size()>0&&a[i]<qmin.back().val) qmin.pop_back(); 33 qmin.push_back(node(i,a[i])); 34 // printf("%d %d ",qmax.front().val,qmin.front().val); 35 if(i>=mid&&qmax.front().val-qmin.front().val<=k) 36 return 1; 37 } 38 return 0; 39 } 40 int main() 41 { 42 read(k);read(n); 43 for(int i=1;i<=n;i++) read(a[i]); 44 int l=1,r=n; 45 int ans=0; 46 while(l<=r) 47 { 48 int mid=l+r>>1; 49 if(check(mid)) ans=mid,l=mid+1; 50 else r=mid-1; 51 } 52 printf("%d",ans); 53 return 0; 54 }