【区间rmq/单调性问题】hdu3530

传送门

题意是找一个最长的区间,使得区间内最大值-最小值 max – min 属于[m,k]

最开始想的二分长度,但实际上并不具有单调性。。
比{1, 0, 1, 3} m = 3 这组数据,当长度为2的时候所有区间都不满足,但长度为3的时候就有一个区间满足了。也就是说不存在短的区间满足,并不代表不存在更长的区间不满足。

导致没有单调性的原因就是题目要求需要满足两个条件,就破坏了单调性,如果题目只有一个限制条件k,那么就是满足单调性的,不存在更短的区间不满足k那么也不存在更长的区间满足k,因为包含段区间的长区间最大值不可能更小,最小值也不可能更大。

因为包含不满足k的区间一定需要更小,而包含不满足m的区间可能变得更大,所以用队列来做。顺序读取数据,让读到一个连续区间不满足k,就从前面缩短区间,直到满足k,当满足m的时候用长度更新答案。

可以用ST表也可以用set。

//1 0 1 3 m = 3 小区间不满足,大区间不一定不满足,不可二分
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
int n, m, k;
int a[maxn];
int main()
{
    while(cin >> n >> m >> k)
    {
        multiset<int> st;
        int l = 1, ans = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            st.insert(a[i]);
            while(*st.rbegin() - *st.begin() > k) st.erase(st.find(a[l++]));
            if(*st.rbegin() - *st.begin() >= m) ans = max(ans, (int)st.size());
        }
        cout<<ans<<endl;
    }
}


发表评论

邮箱地址不会被公开。 必填项已用*标注