「BZOJ3401」[Usaco2009 Mar] Look Up 仰望
Description
约翰的N(1≤N≤105)头奶牛站成一排，奶牛i的身高是Hi(l≤Hi≤1,000,000)．现在，每只奶牛都在向左看齐．对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j． 求出每只奶牛离她最近的仰望对象．
Input
第1行输入N，之后每行输入一个身高．
Output
共N行，按顺序每行输出一只奶牛的最近仰望对象．如果没有仰望对象，输出0．
Sample Input
6
3
2
6
1
1
2
3
2
6
1
1
2
Sample Output
3
3
0
6
6
0
3
0
6
6
0
题解
倒序维护单调递减栈。。。
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,top; int a[100005],s[100005],ans[100005]; int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=n;i;i--) { while(top&&a[s[top]]<=a[i])top--; ans[i]=s[top]; s[++top]=i; } for(int i=1;i<=n;i++)printf("%d\n",ans[i]); return 0; } |
Subscribe
计数器 9786100
OI 课件=>
OI 课件=>