程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2452 (RMQ + 二分)

POJ 2452 (RMQ + 二分)

編輯：C++入門知識

POJ 2452 (RMQ + 二分)

Sticks Problem Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 10141 Accepted: 2682

Description

Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line, represented by S1, S2, S3, ...Sn. After measuring the length of each stick Sk (1 <= k <= n), she finds that for some sticks Si and Sj (1<= i < j <= n), each stick placed between Si and Sj is longer than Si but shorter than Sj.

Now given the length of S1, S2, S3, …Sn, you are required to find the maximum value j - i.

Input

The input contains multiple test cases. Each case contains two lines.
Line 1: a single integer n (n <= 50000), indicating the number of sticks.
Line 2: n different positive integers (not larger than 100000), indicating the length of each stick in order.

Output

Output the maximum value j - i in a single line. If there is no such i and j, just output -1.

Sample Input

Sample Output

1
-1

題意：給一個長度為n的序列其中 Si ~ Sj (1<= i < j <= n)為其子序列問：滿足Si ~ Sj 中任意一個數大於Si 且小於Sj的序列中，j - i的值最大為多少。
解題思路：一開始就沒想過暴力，但是其實暴力是可以過的，坑。。。。。
然而我的方法是用RMQ處理出區間最值，然後暴力掃過去，對每一個數用兩次二分找出這個數所能形成的最大區間。（先假設起點為i）兩次二分作用分別為：
第一次：找出i能作為最小值的最大區間位置（其實這個可以用單調棧來處理）第二次：在第一次找出的區間內尋找出該區間最大值的位置

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define eps 1e-8
const int  inf =  (1<<30) - 10;
using namespace std;

const int maxx = 50000 + 10;
int n;
int a[maxx];

int dpmax[maxx][20];
int dpmin[maxx][20];
int mn[maxx];
inline void init_rmq(int a[],int n){ ///構建rmq
    mn[0]=-1;
    for(int i = 1;i <= n; ++i){
        if((i&(i-1))==0){
            mn[i] = mn[i-1]+1;
        }else{
            mn[i] = mn[i-1];
        }
        dpmax[i][0] = a[i];
        dpmin[i][0] = a[i];
    }
    for(int j = 1;j <= mn[n]; ++j){
        for(int i = 1;i+(1<>1;
                if(min_rmq(i,mid) == a[i]){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            int ll = i;
            int rr = l;
            if(l != i){
                int temp = max_rmq(ll,rr);
                while(ll+1 != rr){
                    int mid = (ll+rr)>>1;
                    if(max_rmq(i,mid) < temp){
                        ll = mid;
                    }else{
                        rr = mid;
                    }
                }
            }
            if(rr-i>ans) ans = rr-i;
        }
        if(ans) printf(%d
,ans);
        else printf(-1
);
    }
    return 0;
}

/**

7
1 2 3 7 4 5 6

*/