[ACM] CSU 1553 Good subsequence(尺取法）

题目地址：?id=1553

给定n的数的序列，求最长连续区间满足区间内的数最大值与最小值的差<=k

(尺取法)

const int maxn=10010;int num[maxn];int n,k;int MIN,MAX;int main(){while(scanf("%d%d",&n,&k)!=EOF){for(int i=1;i<=n;i++)scanf("%d",&num[i]);int l=1,r=1;MAX=MIN=num[1];int ans=1;while(1){if(r>n)break;while(1){MAX=max(MAX,num[r]);MIN=min(MIN,num[r]);if(MAX-MIN<=k&&r<=n)ans=max(ans,r-l+1);if(MAX-MIN<=k)r++;elsebreak;if(r>n)break;}if(r>n)break;bool first=1;while(MAX-MIN>k&&l<r)//l向右跑，Max，Min要重新计算！{l++;if(first){MAX=num[l],MIN=num[l];first=0;}else{MAX=max(MAX,num[l]);MIN=min(MIN,num[l]);}}for(int k=l;k<=r;k++){MAX=max(MAX,num[k]);MIN=min(MIN,num[k]);}if(l==r){r++;MAX=max(MAX,num[r]);MIN=min(MIN,num[r]);}}printf("%d\n",ans);}return 0;}

，听他第二十八次提起童年往事，每年的同一天和他庆祝生日，