STL最后三个点TLE,请问STL怎么用二分找单调栈中第一个比他大的数?
查看原帖
STL最后三个点TLE,请问STL怎么用二分找单调栈中第一个比他大的数?
231543
bloodstalk楼主2022/4/21 16:14

我是一个一个找相同的数的,遇到hack就寄了,请问用STL还有办法吗(STL栈好像没有找位置的)? 代码如下```

#include<bits/stdc++.h>
#define int long long

const int N=5*1e5+1;
using namespace std;

int h[N];
int ans,t;
int n;

stack <int> s;

signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&h[i]);
	for(int i=1;i<=n;i++)
	{
		t=1;
		while(!s.empty() && h[i]>=s.top()) 
		{
			if(s.top()==h[i]) t++;
			ans++;
			s.pop();
		}
		if(!s.empty()) ans++;
		for(int j=1;j<=t;j++) s.push(h[i]);
	}
	printf("%lld",ans);
	return 0;
}
2022/4/21 16:14
加载中...