BZOJ 3401: [Usaco2009 Mar]Look Up 仰望( 单调栈 )

时间:2021-01-01 14:30:38

BZOJ 3401: [Usaco2009 Mar]Look Up 仰望( 单调栈 )

n <= 105 , 其实是10 ^ 5 ....坑...我一开始写了个模拟结果就 RE 了.. 发现这个后写了个单调栈就 A 了...

---------------------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
 
#define rep( i , n ) for( int i = 0 ; i < n ; ++i )
#define clr( x , c ) memset( x , c , sizeof( x ) )
#define Rep( i , n ) for( int i = 1 ; i <= n ; ++i )
 
using namespace std;
 
const int maxn = 100000 + 5;
 
struct node {
int x , h;
};
 
int h[ maxn ];
int ans[ maxn ];
stack< node > S;
 
int main() {
freopen( "test.in" , "r" , stdin );
int n;
cin >> n;
rep( i , n ) scanf( "%d" , &h[ i ] );
clr( ans , 0 );
rep( i , n ) {
while( ! S.empty() && S.top().h < h[ i ] ) {
node o = S.top();
S.pop();
ans[ o.x ] = i + 1;
}
S.push( ( node ) { i , h[ i ] } );
}
rep( i , n ) 
   printf( "%d\n" , ans[ i ] );
return 0;
}

---------------------------------------------------------------------------------------------

3401: [Usaco2009 Mar]Look Up 仰望

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 142  Solved: 85
[Submit][Status][Discuss]

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

Sample Output

3
3
0
6
6
0

HINT

Source