Massive Algorithms: HDU 3530

HDU 3530 - Subsequence

http://acm.hdu.edu.cn/showproblem.php?pid=3530

There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k.

Input

There are multiple test cases.
For each test case, the first line has three integers, n, m and k. n is the length of the sequence and is in the range [1, 100000]. m and k are in the range [0, 1000000]. The second line has n integers, which are all in the range [0, 1000000].
Proceed to the end of file.

Output

For each test case, print the length of the subsequence on a single line.

Sample Input

Sample Output

5
4

给一个序列，t为一个子串中最大值和最小值的差值，要求t在[L,R]之间，求问符合这样的子串最长的长度是多少。

https://blog.csdn.net/Maosghoul/article/details/81204975
首先说一下单调队列的复杂度，是每个数出队入队各一次，复杂度O（n);

下面我们就开始对此题的解法。

我们可以设想，如果有一个，既有标记着位置，又有标记着值得从大到小得队列，和一个从小到大的队列，我们直接比较队列的头部，然后进行出对和入队，这不就可以解决了吗

例如给出一个样例 5 0 0 A[1-n] = {5 , 4 , 2 , 1 , 3}

max单调队列 min单调队列

i==1时 5 5 此时满足答案， ans =1;

i==2时 5 4（5出4入）此时由于5 - 4>区间右值0 因此 max队列的头部出列

i==3时 4 2 （4出2入）此时由于4-2>区间右值0 因此max 队列的头部出列

i==4时 2 1（2出1入) 此时由于2-1>区间右值0 因此max 队列的头部出列

i==5时 3 1 此时由于3-1>区间右值0 因此max 队列的头部出列

然后最后得出的结果是 ans = 1; 输出1；

ps:此题有一个坑就是没有说区间的m 和 K的相对大小，如果K<m 则此区间不存在因此输出为 0了；

https://blog.csdn.net/feizaoSYUACM/article/details/77257351

题目是要求一段区间内最大值与最小值的差不低于m不超过k，那么维护一个递增的单调队列和一个递减的单调队列。凡是差值超过k的就往前挪动，满足条件之后每次得到的一个区间，如果符合差值不低于m的条件，更新区间长度的ans值就行了。

只有通过单调队列扫一遍。

维护一个最大值和一个最小值。

保证最大值-最小值时满足上界条件的。

然后如果下界条件满足就更新答案。
http://kugwzk.info/index.php/archives/1594
维护两个单调队列，分别存到当前i的最大值和最小值。用一个bg变量表示当前区间的起点。当队首的两值差大于k，就需要我们舍弃两个单调队列中更靠前的那个位置(这样可以保证队列的长度求得是最长），并且更新bg。如果队首两值差大于等于M就可以更新答案。
http://www.acmsearch.com/article/show/13474
思路：维护两个单调队列，一个单调递增的队列，一个递减的队列，并且维护一个指针p（代表满足当前序列的最左边的端点，开始时赋值为0）。然后分三种情况讨论当值小于m时，这时候队列中肯定不存在成立的值，所有就必须再继续进队，当刚好成立的时候，更新ans，当大于k的时候，这时候就要把单调队列的头指针出队了，然后这时候必须要选择头指针位置小的那个队列的头指针出队，因为你把位置大的出队的话位置小的那个元素有被用到，这时候明显不符合实际，因为位置小的存在，位置大的必定也存在，所以这时候必须把位置小的出队，然后更新指针p = 出队的那个元素位置加1。

这是做的第一道单调队列，这道题目中单调队列里面存的是数组元素的下标，当是它是维护的是数组值的单调性，感觉最重要的一点是队列里面的下标值肯定都是从小到大的，
因为在进队过程中，是把前面不合符的都出队了，所以它所在的位置肯定是最右边的，这样就能保证了i-p是最优答案了，因为p这时候是为队头位置+1，而出队的队头位置是最小的。所以p这是是最小的。
https://saisin.wordpress.com/2011/03/31/hdu-3530-%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97/

状态表示：F[i]：以i为结束点的序列满足m,k的条件的最大值。如果从后向前扫描统计最大值和最小值，这样时间复杂度为O(n*n).

通过分析发现：

max[i-1，j+1] >= max[i,j] and min[i-1,j+1] <= min[i,j]；令p[i,j] = max[i,j] – min[i,j]

即：设p[i,j]随着i的增加，p[i,j]下降；随着j的增加，p[i,j]增加。

1.F[j] = min{i: p[i,j] <= k},i的取值范围，随着j的增加，i值不减。if: p[i,j] > k then:p[i,j+1] >k

2.当得到p[i,j] <= k的最小i后，如果p[i,j] < m 那么 p[i+1,j] <m,即：如果满足k后如果不满足m，那么后面的值都不满足。

通过以上的分析，我们的目标就是找到关于j的p[i,j] <= k的最小i,这个值i值取值范围只增不减。

于是可以使用单调队列来优化，设计一个i值指针，代表对于j可以取的最小值为i。两个单调队列，分别表示i以后到j的最大值和最小值。如果当前的i值，p[i,j] > k,那么取下一个最大值或者最小值，由于要去i值最小，i值增加到两个队列中小的下标。在求最小i值的过程中统计对于每个j的最长序列值。

算法的时间复杂度降到了O(n).

https://xuela-net.iteye.com/blog/1906290
https://www.zybuluo.com/lychee123/note/633946


int a[100005];
int main()
{
    int n,m,k,i;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        if(m>k)
        {
            printf("0\n");
            continue;
        }
        deque<int>q1;///维护最大值（从头到尾从大到小）
        deque<int>q2;///维护最小值
        int last=-1,ans=0;
        for(i=0;i<n;i++)
        {
            while(!q1.empty()&&a[i]>a[q1.back()])
                q1.pop_back();
            while(!q2.empty()&&a[i]<a[q2.back()])
                q2.pop_back();
            q1.push_back(i);
            q2.push_back(i);
            while(!q1.empty()&&a[q1.front()]-a[q2.front()]>k)
            {
                if(q1.front()>q2.front())
                {
                    last=q2.front();
                    q2.pop_front();
                }
                if(q1.front()<q2.front())
                {
                    last=q1.front();
                    q1.pop_front();
                }
            }
            if(!q1.empty()&&!q2.empty()&&a[q1.front()]-a[q2.front()]>=m)
                ans=max(ans,i-last);
        }
        printf("%d\n",ans);
    }
    return 0;
}

const int MAXN=100010;
int a[MAXN];
int q1[MAXN],q2[MAXN];//q1是维护最大值，q2维护最小值
int n,m,k;


int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    while(scanf("%d%d%d",&n,&m,&k)==3)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int ans=0;
        int rear1,front1,rear2,front2;
        rear1=front1=0;
        rear2=front2=0;
        int now=0;
        for(int i=1;i<=n;i++)
        {
            while(front1<rear1 && a[q1[rear1-1]]<a[i])rear1--;
            q1[rear1++]=i;
            while(front2<rear2 && a[q2[rear2-1]]>a[i])rear2--;
            q2[rear2++]=i;
            while(front1<rear1 && front2<rear2 && a[q1[front1]]-a[q2[front2]]>k)
            {
                if(q1[front1]<q2[front2])
                {
                    now=q1[front1];
                    front1++;
                }
                else
                {
                    now=q2[front2];
                    front2++;
                }
            }
            if(front1<rear1 && front2<rear2 && a[q1[front1]]-a[q2[front2]]>=m)
                ans=max(ans,i-now);
        }
        printf("%d\n",ans);
    }
    return 0;
}

http://www.voidcn.com/article/p-mkqjqcob-bnv.html

二分答案，线段树判断答案，check的时候需要判断三种情况：
第一种，t的最大值在[L,R]中；
第二种，t的最大值

HDU 3530 - Subsequence

Labels

Popular Posts