手打连表 , 用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;
}
请各位 大佬