程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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

4
5 4 3 6
4
6 5 4 3

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

*/
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved