poj 2452(RMQ+二分查找)

题目链接：

题意：在区间[1,n]上找到满足 a[i]<a[k]<a[j] (i<=k<=j) 的最大子区间（j-i）如不存在输出 -1.

思路：枚举i,找到 i右边第一个不大于（不是小于） a[i]的数a[k]（二分查找+RMQ某段区间的最小值是否小于a[i].最后确定到一个点）,于是
我们可以得到在区间[i,k-1]范围内的数都会大于 a[i] ,所以对于下标i，它对应的最长区间必定在[i,k-1]之间。

所以，我们只要找到这个区间最大值 a[j] （这里又要用到RMQ查找区间最大值下标）所以我们可以得到相对于点 i，其对应的最长子区间是[i,j]

例： 2 3 4 5 3 2 6 7

我们先枚举下标1 ，算出右边不大于它的点是 a[6] = 2

然后对于区间 2 3 4 5 3 2 最大值是 a[4] = 5 ，所以相对于下标1最长的区间是 1 - 4，依此类推。

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

const int N = ;

///储存区间最大最小值的下标

int max_dp[*N][];

int min_dp[*N][];

int a[N];

int MAX(int i,int j){

    if(a[i]>a[j]) return i;

    return j;

}

int MIN(int i,int j){

    if(a[i]>a[j]) return j;

    return i;

}

void init_RMQ(int n){

    for(int i=;i<=n;i++){

        max_dp[i][] = min_dp[i][]=i;

    }

    for(int j=;(<<j)<=n;j++){

        for(int i=;i+(<<j)-<=n;i++){

          max_dp[i][j] = MAX(max_dp[i][j-],max_dp[i+(<<(j-))][j-]);

          min_dp[i][j] = MIN(min_dp[i][j-],min_dp[i+(<<(j-))][j-]);

        }

    }

}

int MAX_RMQ(int l,int r){

    int k  = (int)(log(r-l+1.0)/log(2.0));

    return MAX(max_dp[l][k],max_dp[r-(<<k)+][k]);

}

int MIN_RMQ(int l,int r){

    int k = (int)(log(r-l+1.0)/log(2.0));

    return MIN(min_dp[l][k],min_dp[r-(<<k)+][k]);

}

int binary(int value,int l,int r){

    while(l<=r){

        if(l==r) return l;

        int mid = (l+r)>>;

        //printf("MIN_RMQ:%d\n",a[MIN_RMQ(l,mid)]);

        if(value<a[MIN_RMQ(l,mid)]){

            l = mid+;

        }else r = mid;

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF){

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

        }

        init_RMQ(n);

        int ans = ;

        for(int i=;i<=n;i++){

            int value = a[i];

            int k = binary(value,i+,n);

            int j = MAX_RMQ(i,k);

            //printf("%d %d %d\n",i,k,j);

            if(a[j]>a[i])

            ans = ans>j-i?ans:j-i;

        }

        if(ans==) printf("-1\n");

        else printf("%d\n",ans);

    }

}

巴特西

poj 2452(RMQ+二分查找)

最新文章

热门文章