WOJ1019 所有的M数

题目链接：###

题目分析：###

单调栈维护，读一个进来，如果前面的比它大就弹出来，然后压栈里（反正它在最右边）

压进栈里输出它前面那个数就好了

O(n)扫一遍就能过

真的水得不能再水的题了……我只是水篇博客

代码：###

#include<bits/stdc++.h>

#define MAXN (500000+5)

using namespace std;

inline int read(){

    int f=1,cnt=0;char c;

    c=getchar();

    while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}

    while(isdigit(c)){cnt=cnt*10+c-'0';c=getchar();}

    return cnt*f;

}

int sta[MAXN],n,top=0;

int x;

int main(){

	n=read();

	sta[top]=0;

	for(register int i=1;i<=n;i++){

		x=read();

		if(sta[top]<x){

			sta[++top]=x;

			printf("%d ",sta[top-1]);

		}

		else{

			while(sta[top]>=x&&top)top--;

			sta[++top]=x;

			printf("%d ",sta[top-1]);

		}

	}

	return 0;

}

巴特西

WOJ1019 所有的M数

题目链接：###

题目分析：###

代码：###

最新文章

热门文章