scan sof microsoft 区间最值 bzoj turn 区间 color
题目描述
Tz 又耍畸形了!!他要当飞行员,他拿到了一个飞行员测试难度序列,他设定了一个难度差的最大值,在序列中他想找到一个最长的子串,任意两个难度差不会超过他设定的最大值。耍畸形一个人是不行的,于是他找到了你。
输入
输入:第一行两个有空格隔开的整数 k(0<=k<=2000,000,000),n(1<=n<=3000,000),k 代表 Tz 设定的最大值,n 代表难度序列的长度。第二行为 n 个由空格隔开的整数 ai(1<=ai<=2000,000,000),表示难度序列。
输出
输出:最大的字串长度。
样例输入
3 9
5 1 3 5 8 6 6 9 10
样例输出
4
题解
双指针法 + STL-set
考虑随着做端点向右移动,右端点的选择是单调不降的。所以可以使用双指针法扫出以某个点为左端点的最长的区间。
此时需要维护区间最值,可以使用单调队列来在线性时间内解决。当然本题也可以像我一样使用 set 水过。
- #include < cstdio > #include < set > using namespace std;
- multiset < int > s;
- int a[3000010];
- int main() {
- int k,
- n,
- i,
- p,
- ans = 0;
- scanf("%d%d", &k, &n);
- for (i = 1; i <= n; i++) scanf("%d", &a[i]);
- for (i = p = 1; i <= n; i++) {
- while (p <= n && (s.empty() || max( * (--s.end()), a[p]) - min( * s.begin(), a[p]) <= k)) s.insert(a[p++]);
- ans = max(ans, p - i),
- s.erase(s.find(a[i]));
- }
- printf("%d\n", ans);
- return 0;
- }
【bzoj2096】[Poi2010]Pilots 双指针法 + STL-set
来源: http://www.bubuko.com/infodetail-2278987.html