洛谷 P2947 [USACO09MAR]向右看齐Look Up
程序员文章站
2022-03-20 16:34:22
[TOC] 题目 "戳" 思路 单调栈裸题 $Code$ cpp include include include include include define MAXN 100001 define rr register using namespace std; int n,ans[MAXN]; s ......
目录
题目
思路
单调栈裸题
$code$
#include<stack> #include<cstdio> #include<string> #include<cstring> #include<iostream> #define maxn 100001 #define rr register using namespace std; int n,ans[maxn]; struct mu{ int num,h; }mumumu[maxn]; stack<mu> sss; inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } int main(){ n=read(); for(rr int i=1;i<=n;++i){ mumumu[i].num=i; mumumu[i].h=read(); } for(rr int i=n;i>=1;--i){ if(i==n){ sss.push(mumumu[n]); ans[i]=0; }else{ while(mumumu[i].h>=sss.top().h){ sss.pop(); if(sss.empty()) break; } if(sss.empty()) ans[i]=0; else ans[i]=sss.top().num; sss.push(mumumu[i]); } } for(rr int i=1;i<=n;++i){ printf("%d\n",ans[i]); } return 0; }