Sticks Problem POJ – 2452 (线段树)

作者: zqqian 分类: 算法 发布时间: 2017-08-13 00:06
Sticks Problem
Time Limit: 6000MSMemory Limit: 65536K
Total Submissions: 10724Accepted: 2855

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

这个题算法也比较简单,就是先找出来整个数组中的最大值所在的位置P(max)和最小值所在的位置P(min)。

显然,在P(min)<P(max)的情况下,P(max)-P(min)一定是满足条件的一个区间。

但是并不一定是最大区间。

因为在[left,P(min)-1],和[P(max)+1,right]这两个区间中任然存在满足条件的区间。

这时只要递归查找两个区间并且与之前的结果取最大值就是答案。

但是如果用普通的算法计算区间的最大值和最小值的位置肯定会超时。

所以采用线段树的方法来计算。

用四个数组来分别保存一个区间的最大值和最小值和最大值的位置和最小值的位置。

然后算法的时间复杂度就大大降低了。

#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
int a[50007];	
int t;
int b[150007];
int bb[150007];
int c[150007];
int cc[150007];
int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}
void build(int num,int l,int r){
	if(l==r){
		b[num]=a[l];
		c[num]=a[r];
		bb[num]=cc[num]=l;
		return;
	}
	build(num<<1,l,(l+r)/2);
	build(1+(num<<1),((l+r)/2)+1,r);
	b[num]=max(b[num<<1],b[1+(num<<1)]);
	c[num]=min(c[num<<1],c[1+(num<<1)]);
	if(b[num<<1]>b[1+(num<<1)]){
		bb[num]=bb[num<<1];
	}else{
		bb[num]=bb[1+(num<<1)];
	}
	if(c[num<<1]<c[1+(num<<1)]){
		cc[num]=cc[num<<1];
	}else{
			cc[num]=cc[1+(num<<1)];
	}
	return;
}
int maxnum(int num,int L,int R,int l,int r){
	//cout<<num<<" "<<L<<" "<<R<<" "<<endl;
	
	if(l<=L&&r>=R){
	//	cout<<num<<" "<<bb[num]<<endl;
		return bb[num];
	}
	int mid=(L+R)/2;
	int loc=0;
	if(l<=mid){
		loc=maxnum(num<<1,L,(R+L)/2,l,r);
	//	cout<<"loc"<<loc<<
	}
	if(r>mid){
		if(loc){
			int temloc=maxnum(1+(num<<1),mid+1,R,l,r);
			if(a[loc]<a[temloc]){
			//	cout<<a[loc]<<" 1 1 1 "<<a[temloc]<<endl; 
				loc=temloc;
			}
		}else{
			loc=maxnum(1+(num<<1),mid+1,R,l,r);
		}
	}
	return loc;
	
}
int minnum(int num,int L,int R,int l,int r){
	
	
	if(l<=L&&r>=R){
		return cc[num];
	}
	int mid=(L+R)/2;
	int loc=0;
	if(l<=mid){
		loc=minnum(num<<1,L,(R+L)/2,l,r);
		
	}
	if(r>mid){
		if(loc){
			int temloc=minnum(1+(num<<1),mid+1,R,l,r);
			if(a[loc]>a[temloc]){
				loc=temloc;
			}
		}else{
			loc=minnum(1+(num<<1),mid+1,R,l,r);
		}
	}
	return loc;
} 
int sum(int l,int r){
	if(r<=l||r>t||l<1){
		return -1;
	}
	
	int maxi=maxnum(1,1,t,l,r);
	int mini=minnum(1,1,t,l,r);
//	cout<<maxi<<" "<<mini<<" "<<l<<" "<<r<<endl;
	if(maxi>mini){
		int len=maxi-mini;
		len=max(len,sum(l,mini-1));
		len=max(len,sum(maxi+1,r));
		return len;
	}
	if(maxi<mini){
		int len=sum(maxi+1,mini-1);
			len=max(len,sum(l,maxi));
			len=max(len,sum(mini,r));
			return len;
	}else{
		return -1;
	}
}
int main()
{
ios::sync_with_stdio(0);
	while(cin>>t){
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		memset(bb,0,sizeof(bb));
		memset(cc,0,sizeof(cc));
		for(int i=1;i<=t;i++){
			cin>>a[i];		
		}
		build(1,1,t);

//cout<<minnum(1,1,t,1,2);

cout<<sum(1,t)<<endl;
		

		
	}
	
	
	
	return 0;
 } 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注