单调栈真的很好用呢!
P2947 [USACO09MAR]向右看齐Look Up
题目描述
Farmer John's N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once again standing in a row. Cow i has height H_i (1 <= H_i <= 1,000,000).
Each cow is looking to her left toward those with higher index numbers. We say that cow i 'looks up' to cow j if i < j and H_i < H_j. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.
Note: about 50% of the test data will have N <= 1,000.
约翰的N(1≤N≤10^5)头奶牛站成一排,奶牛i的身高是Hi(l≤Hi≤1,000,000).现在,每只奶牛都在向右看齐.对于奶牛i,如果奶牛j满足i<j且Hi<Hj,我们可以说奶牛i可以仰望奶牛j. 求出每只奶牛离她最近的仰望对象.
Input
输入输出格式
输入格式:
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains the single integer: H_i
第 1 行输入 N,之后每行输入一个身高 H_i。
输出格式:
* Lines 1..N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.
共 N 行,按顺序每行输出一只奶牛的最近仰望对象,如果没有仰望对象,输出 0。
输入输出样例
3 3 0 6 6 0
分析一下题目就不难想到:我们可以维护一个非递增的单调栈,如果栈为空或者新的元素的值小于等于栈顶元素,我们就直接把这个元素压入栈,否则就弹出栈顶元素,并把栈顶元素的ans值记为新的元素的下标。特别地,如果这个元素没有仰望对象,这该怎么办呢?其实也不难,我们可以在栈的最后强行加入一个极大值,这样就可以保证栈中的所有元素都可以出栈,在输出答案的时候,如果ans值为n+1那么就说明这个元素没有仰望对象,输出0。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cmath> 5 #include<cstring> 6 #include<queue> 7 #include<stack> 8 #include<algorithm> 9 #define maxn 100005 10 using namespace std; 11 12 stack<int>s; 13 14 inline int read() 15 { 16 char c=getchar(); 17 int res=0,x=1; 18 while(c<'0'||c>'9') 19 { 20 if(c=='-') 21 x=-1; 22 c=getchar(); 23 } 24 while(c>='0'&&c<='9') 25 { 26 res=res*10+(c-'0'); 27 c=getchar(); 28 } 29 return x*res; 30 } 31 32 int n,aa; 33 int a[maxn],ans[maxn]; 34 35 int main() 36 { 37 n=read(); 38 for(int i=1;i<=n;i++) 39 { 40 aa=read(); 41 a[i]=aa; 42 } 43 a[n+1]=10000005;//这里赋一个极大值。 44 for(int i=1;i<=n+1;i++) 45 { 46 if(s.empty()||a[s.top()]>=a[i])//栈为空或者当前元素小于等于栈顶元素 47 { 48 s.push(i);//入栈 49 } 50 else 51 { 52 while(!s.empty()&&a[s.top()]<a[i])//否则就出栈 53 { 54 ans[s.top()]=i;//更新ans值 55 s.pop(); 56 } 57 s.push(i); 58 } 59 } 60 for(int i=1;i<=n;i++) 61 { 62 if(ans[i]==n+1)//特判是否输出0 63 printf("0 "); 64 else printf("%d ",ans[i]); 65 } 66 return 0; 67 }
--snowy
2019-01-18 11:44:51