HDU3530 子序列

题目大意:给出一串长度为n的整数串,求最长的一个连续子序列,满足该序列中最大的元素与最小的元素之差大于等于m, 并且小于等于k。n<=100000

分析:维护两个单调队列,一个递增的,维护最小值,一个递减的,维护最大值。设f[i]表示当前i所在区间的长度,若a[i]在最大值和最小值之间,则当前元素可以加入到上一个元素的区间中,即f[i]=f[i-1]+1;若a[i]>最大值,则当前区间的上限变为a[i],下限在范围[a[i]-m,a[i]-k]之内。在递增的单调队列中不断的删除队头,直到找到一个在范围[a[i]-m,a[i]-k]内的队头元素位置,找不到则f[i]=0,否则f[i]的值为队头的位置到i的位置的元素个数,要记得将a[i]加入到两个队列的队尾。

若a[i]<最小值,方法是对称的,即在递减的队列中去查找队头满足[[a[i]+m,a[i]+k],不满足即删除队头。f[i]的长度为队头的位置到i的位置的元素个数,或为0.

上一篇:Django学习-4-request获取数据


下一篇:python笔记-20 django进阶 (model与form、modelform对比,三种ajax方式的对比,随机验证码,kindeditor)