随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 2452 Sticks Problem

题目链接:http://poj.org/problem?id=2452
/*
题意:
    给定一个长度为N(N <= 50000)的数列Si,要求找到Si和Sj(1 <= i < j <= N)
使得所有的Sk(i < k < j)大于Si并且小于Sj。如果能找到这样的对数,输出最大的
j-i,否则输出-1。

解法:
二分+线段树 或者 二分+RMQ

思路:
    首先考虑最暴力的情况,自然是枚举i和j,然后判i+1到j-1这些数是否满足条件,
如果满足则更新j-i,这样的复杂度是O(n^3)的,时间上显然说不过去。然后试着降掉
一维,同样枚举i和j,然后在判断是否满足条件时,利用线段树求区间最值,这样的复
杂度就降到了O(n^2logn),然而N的数据量还是不允许我们这么做,于是只能试着寻找
O(nlogn)的算法。
    那么我们尝试枚举一个j,看看能不能通过它来确定i,这里有一条很明显的性质,
就是如果Si到Sj-1都小于Sj那么Si+1到Sj-1必然也都小于Sj,这条性质可以让我们二分
枚举i的左边界t,采用二分找到最小的t使得St-1 >= Sj,也即St < Sj(t <= i < j),
找的过程可以采用线段树求出区间最大值进行比较,然后问题就转化成了在以下数列:
St St+1  Sj-1 Sj 找到最小的i(t <= i < j)使得Si+1到Sj都大于Si,很明显,又
是一个区间最值的问题,利用线段树求出[t, j-1]最小值的下标,就是我们要求的i,
如果有多个,必须选择最靠近j的,这是显然的。这样总的复杂度就降到O(n(logn)^2),
当然求最值的时候可以采用RMG代替线段树,RMG的询问复杂度是O(1)的。
*/

#include 
<iostream>

using namespace std;

#define maxn 50010

typedef 
int Tree_Index;

struct Tree {
    
int Max, Min;
    
int MinPos;    // 最小值所在位置,相同的取靠右边的
    
// 区间最值
}
T[4*maxn];

int val[maxn], n;

void Build(Tree_Index p, int l, int r) {
    
if(l == r) {
        T[p].Max 
= T[p].Min = val[l];
        T[p].MinPos 
= l;
        
return ;
    }

    
int mid = (l + r) >> 1;
    Build(  p
<<1,     l, mid);
    Build(p
<<1|1, mid+1,   r);
    
    T[p].Max 
= T[p<<1].Max > T[p<<1|1].Max ? T[p<<1].Max : T[p<<1|1].Max;
    T[p].Min 
= T[p<<1].Min < T[p<<1|1].Min ? T[p<<1].Min : T[p<<1|1].Min;
    T[p].MinPos 
= T[p<<1].Min < T[p<<1|1].Min ? T[p<<1].MinPos : T[p<<1|1].MinPos;
}


Tree_Index Query(Tree_Index p, 
int l, int r, int a, int b, bool bMin) {
    
if(l == a && b == r) {
        
return p;
    }

    
int mid = (l + r) >> 1;
    
if(b <= mid) {
        
return Query(p<<1, l, mid, a, b, bMin);
    }
else if(a >= mid + 1{
        
return Query(p<<1|1, mid+1, r, a, b, bMin);
    }
else {
        Tree_Index p1 
= Query(p<<1, l, mid, a, mid, bMin);
        Tree_Index p2 
= Query(p<<1|1, mid+1, r, mid+1, b, bMin);
        
if(bMin) {
            
return T[p1].Min < T[p2].Min ? p1 : p2;
        }
else
            
return T[p1].Max > T[p2].Max ? p1 : p2;
    }

}


int binary(int rIdx) {
    
int l = 1;
    
int r = rIdx;
    
int m;
    
int ans = rIdx;
    
while(l <= r) {
        m 
= (l + r) >> 1;
        
if(m == rIdx) {
            l 
= m + 1;
            
continue;
        }

        Tree_Index ansIdx 
= Query(11, n, m, rIdx-1false);
        
if(T[ansIdx].Max < val[rIdx]) {
            r 
= m - 1;
            
if(m < ans) {
                ans 
= m;
            }

        }
else
            l 
= m + 1;
    }

    
return ans;
}


int main() {
    
int i;
    
while(scanf("%d"&n) != EOF) {
        
for(i = 1; i <= n; i++{
            scanf(
"%d"&val[i]);
        }

        Build(
11, n);
        
int Max = -1;
        
for(i = n; i >= 2; i--{
            
int v = binary(i);
            
if(v != i) {
                
if(i - v < Max)
                    
continue;
                Tree_Index p 
= Query(11, n, v, i, true);
                
if(T[p].MinPos != i) {
                    
if(i - T[p].MinPos > Max)
                        Max 
= i - T[p].MinPos;    
                }

            }

        }

        printf(
"%d\n", Max);
    }

    
return 0;
}


posted on 2011-03-29 18:05 英雄哪里出来 阅读(1452) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理