CSP-J T4求助
  • 板块灌水区
  • 楼主Link_Cut_qwq
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/10/24 08:42
  • 上次更新2023/11/4 02:30:53
查看原帖
CSP-J T4求助
546289
Link_Cut_qwq楼主2021/10/24 08:42

为啥我全TLE?

#include <bits/stdc++.h> 
#define N 200020
using namespace std;

int n, a[N], nxt[N], las[N], cnt, l[N], sum, to[N], r[N], opt[N];

int main ()
{
	cin >> n; a[0] = -1;
	for (int i = 1; i <= n; i++)
	{
		scanf ("%d", &a[i]);
		if (a[i] != a[i-1])
		{
			nxt[cnt] = ++cnt, las[cnt] = cnt - 1;
			l[cnt] = i, r[cnt-1] = i - 1; opt[cnt] = a[i];
		} else to[i-1] = i;
	}
	opt[0] = 10;
	while (sum < n)
	{
		for (int i = nxt[0]; i; i = nxt[i])
		{
			cout << l[i] << " "; l[i] = to[l[i]]; sum++;
		}
		for (int i = nxt[0]; i; i = nxt[i])
		{
			if (opt[las[i]] == opt[nxt[i]] && l[las[i]] && l[nxt[i]] && !l[i])
			{
				nxt[las[i]] = nxt[nxt[i]], las[nxt[nxt[i]]] = las[i];
				to[r[las[i]]] = l[nxt[i]], r[las[i]] = r[nxt[i]];
			} else if (!l[i])
			{
				nxt[las[i]] = nxt[i], las[nxt[i]] = las[i];
			}
		}
		cout << endl;
	}
	return 0;
}

2021/10/24 08:42
加载中...