Sticks Problem
Time Limit: 6000MS Memory Limit: 65536K
Total Submissions: 10574 Accepted: 2814
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 Source 分析:首先用单调栈维护出单调递增的序列。 然后RMQ区间最大值。 RMQ用线段树处理。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include<cstdio>//poj2452 by:uncle-lu #include<algorithm> using namespace std; int n; namespace again{ int line[50010]; struct node{ int num,sit; }_stack[50010]; int last[50010]; int tree[150010]; void build_tree(int step,int x,int y) { if(x==y) { tree[step]=x; return ; } int mid=(x+y)>>1; build_tree(step<<1,x,mid); build_tree(step<<1|1,mid+1,y); tree[step]=line[tree[step<<1]]>line[tree[step<<1|1]] ? tree[step<<1] : tree[step<<1|1]; return ; } int find_tree(int step,int x,int y,int l,int r) { if(l<=x&&r>=y){ return tree[step]; } int mid=(x+y)>>1; if(l>mid) { return find_tree(step<<1|1,mid+1,y,l,r); } if(r<=mid){ return find_tree(step<<1,x,mid,l,r); } int fir=find_tree(step<<1|1,mid+1,y,l,r); int sec=find_tree(step<<1,x,mid,l,r); return line[fir]>line[sec] ? fir : sec; } int main() { for(int i=1;i<=n;++i) { scanf("%d",&line[i]); } int head=0; for(int i=1;i<=n;++i) { if(_stack[head].num<line[i]) { _stack[++head].num=line[i]; _stack[head].sit=i; continue; } else { while(head>0&&_stack[head].num>=line[i]) { last[_stack[head].sit]=i-1; --head; } _stack[++head].num=line[i]; _stack[head].sit=i; } } while(head>0) { last[_stack[head].sit]=n; --head; } build_tree(1,1,n); int ans=-1; for(int i=1;i<=n;++i) { ans=max(ans,find_tree(1,1,n,i,last[i])-i); } printf("%d\n",!ans ? -1 : ans); return 0; } } int main() { while(~scanf("%d",&n)) { again::main(); } return 0; } |
