hdu 3530 Subsequence

Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3496    Accepted Submission(s): 1128

Problem Description 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

5 0 0
1 1 1 1 1
5 0 3
1 2 3 4 5
        

Sample Output

5
4
        

Source 2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU  

Recommend zhengfeng  思路： 1.假设我们现在知道序列（i,j）是符合标准的，那么如果第j+1个元素不比（i,j）最大值大也不比最小值小，那么(i,j+1)也是合法的

2.如果（i,j）不合法的原因是差值比要求小，那在（i,j）范围内的改动是无效的，需要加入j+1元素充当最大值或者最小值才可能获得合法的序列

3.假设序列（i,j）的差值比要求大，那么我们必须将其中的最大值或者最小值从序列中删除出去，才可能获得一个合法的序列，只往里加入元素是不可能令序列合法的

基于以上几点考虑，我们可以利用单调队列完成我们的算法。

设定一个变量ST作为当前合法序列的开端(对于一个序列（i,j)，其对应的ST为i-1)，初始值是0

设f[i]是以第i个元素结尾的最长合法序列长度，我们把i加入两个单调队列中维护，一个维护i之前的最小值，一个是最大值。 用两个单调队列一个维护最大值。一个维护最小值。再枚举区间。

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int a[1000100],hmax,tmax,hmin,tmin,l,r,n,m,k;//hmax,tmax为最大值单调队列的头和尾。后面的同理
struct node
{
    int val;//存值
    int id;//存下标
} q_max[1000100],q_min[1000100];
int main()
{
    int i,ans,ma,mi,temp;

    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        //getchar();
        ans=0;
        hmax=tmax=0;
        hmin=tmin=0;
        l=r=1;//l和r枚举区间
        q_max[tmax].id=q_min[tmin].id=1;
        q_max[tmax].val=q_min[tmin].val=a[1];
        while(r<=n)
        {
            while(q_max[hmax].id<l)//不满足范围的就出队
                hmax++;
            ma=q_max[hmax].val;
            while(q_min[hmin].id<l)
                hmin++;
            mi=q_min[hmin].val;
            //printf("%d->%d  max:%d min:%d\n",l,r,ma,mi);
            //getchar();
            temp=ma-mi;
            if(temp>k)//比k大只能把l往右移
                l++;
            else
            {
                if(temp>=m&&temp<=k&&r-l+1>ans)//若一直无解则答案为0
                    ans=r-l+1;
                r++;
                while(tmax>=hmax&&q_max[tmax].val<a[r])//把新的元素入队
                    tmax--;
                q_max[++tmax].id=r;
                q_max[tmax].val=a[r];
                while(tmin>=hmin&&q_min[tmin].val>a[r])
                    tmin--;
                q_min[++tmin].id=r;//开始偷懒直接把上面的代码贴下来忘了改成q_max搞死人了。
                q_min[tmin].val=a[r];//哎。。。再不能这么粗心了。。。
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
6 1 5
234452 12 14 234 2345 45454
*/
           

改了个地方后的代码

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int a[1000100],hmax,tmax,hmin,tmin,l,r,n,m,k;
struct node
{
    int val;
    int id;
} q_max[1000100],q_min[1000100];
int minn(int a,int b){ return a<b?a:b; }
int main()
{
    int i,ans,ma,mi,temp;

    while(~scanf("%d%d%d",&n,&m,&k))
    {
        ans=0;
        hmax=tmax=0;
        hmin=tmin=0;
        l=r=1;
        q_max[tmax].id=q_min[tmin].id=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            while(tmax>=hmax&&q_max[tmax].val<a[r])
                    tmax--;
                q_max[++tmax].id=r;
                q_max[tmax].val=a[r];
                while(tmin>=hmin&&q_min[tmin].val>a[r])
                    tmin--;
                q_min[++tmin].id=r;//开始偷懒直接把上面的代码贴下来忘了改成q_max搞死人了。
                q_min[tmin].val=a[r];//哎。。。再不能这么粗心了。。。
        }
        while(r<=n)
        {
            while(q_max[hmax].id<l)
                hmax++;
            ma=q_max[hmax].val;
            while(q_min[hmin].id<l)
                hmin++;
            mi=q_min[hmin].val;
            temp=ma-mi;
            if(temp>k)
                l=minn(q_max[hmax].id,q_min[hmin].id)+1;
            else
            {
                if(temp>=m&&temp<=k&&r-l+1>ans)//若一直无解则答案为0
                    ans=r-l+1;
                r++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
6 1 5
234452 12 14 234 2345 45454
*/