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

本文主要是介绍[ACM] CSU 1553 Good subsequence(尺取法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：http://acm.csu.edu.cn/OnlineJudge/problem.php?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;
}

 

这篇关于[ACM] CSU 1553 Good subsequence(尺取法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---