65分单调栈,没有TLE,求调,悬关
查看原帖
65分单调栈,没有TLE,求调,悬关
788733
xawmh2023楼主2024/11/6 12:35
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int r[N];
bool st[N];
int stk[N],tt = 0;
int main()
{
//	1 2 3 1 2
//	1 1 1 1 1
//	0 0 2 0 3
//	1 1 0 0 0
//freopen("data.in","r",stdin);
	int n;
	cin >>n;
	int s = 0;
	memset(st,1,sizeof st);
	for (int i = 1;i <= n;i ++)
	{
		cin >> r[i];
	}
	int mins = 1e9;
	for (int i = 1;i <= n;i ++)
	{
		mins = min(mins,r[i]);
	}
	sort(r + 1,r + 1 + n);
	stk[++tt] = 0;
	for (int i = 1;i <= n;i ++)
	{
		//cout << tt << ' ' <<stk[tt] << endl;
		if (r[i] == mins)
		{
			stk[++tt] = i;
			continue;
		}
		while (r[stk[tt]] == r[i] && tt >= 0) tt--;
		st[stk[tt]] = false;
		tt --;
		stk[++tt] = i;
	}
	for (int i = 1;i <= n;i ++)
		if (st[i])
			s ++;
	cout <<s << endl;
	return 0;
}

单调栈大代码求调,悬关!

2024/11/6 12:35
加载中...