手打链表TLE (60分大关 (#6#8#9#10 ))
查看原帖
手打链表TLE (60分大关 (#6#8#9#10 ))
947873
RedWen_shuo楼主2024/5/23 18:30

手打连表 , 用STL链表都超时 , 有没有解决的方法

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

using namespace std;

const int N = 6e5 + 100;

struct re{
	ll x, y; // 表示 编号 和 类型 (0 或 1) 
	ll pre, nex; // 前驱 ,后继 
};
ll n, h = -1; // h 表示 指针 
re v[N]; // 链表 

void erase_list(ll x){ // 删除 x 点 
	if (v[x].pre == 0) h = v[x].nex;
	v[v[x].pre].nex = v[x].nex, v[v[x].nex].pre = v[x].pre;
}

int main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);

	cin >> n;
	int x, cnt = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> x;
		if (i != n){ // 导入前驱 , 后继 
			v[++ cnt].x = x, v[cnt].y = i, v[cnt].pre = i - 1, v[cnt].nex = i + 1;
			if (i == 1) h = i;
		}else 
			v[++ cnt].x = x, v[cnt].y = i, v[cnt].pre = i - 1, v[cnt].nex = -1;
	
//		cout << i << ":   " << v[cnt].pre << " & " << v[cnt].nex << "\n";
	}
	
	bool b = 0;
	while (cnt){ // 停止条件 : 链表为空 
		ll o = -1, b = 0; // 表示初始化 , b 表示有输出, o 代表 前一个数的类型 (0 或 1) 
		
		for (ll i = h; i != -1;){ // 链表遍历(list 超时, 手打 list 也超时) 
			if (v[i].x != o){ // 前后类型不同输出 
				cnt	--;
				o = v[i].x;
				cout << i << " ";
				erase_list(i); // 删除指令 
				b = 1;
//				cout << "////////////////////////////////////////////////////////////\n";
//				for (int j = h; v[j].nex != -1; j = v[j].nex){
//					cout << v[j].y << ":   " << v[j].pre << " & " << v[j].nex << "\n";
//				}
//				cout << "------------------------------------------------------------\n";
			} else i = v[i].nex;
		}
		
		if (b)
		cout << "\n";
	}
	
	return 0;
}

请各位 大佬

指点明津

2024/5/23 18:30
加载中...