PTA Basic 1075

1075 链表元素分类 - PAT (Basic Level) Practice （中文） (pintia.cn) 一开始是拿 map 读入链表然后按照地址得出链表的各个节点顺序，本题的数据量级为 ${10}^5$，会超时，因为 map 的查找耗时 $O(logn)$，对于 ${10}^5$ 数据来说，需要处理 ${10}^{5}lo{g}_2{10}^5\approx 1.6\times {10}^6$ 次，写入大概也在这个次数。 值得注意的是，vector 的 erase 操作是 $O(n)$ 的，因为它是连续存储的，所以在对容器进行遍历处理的时候，只要有极少数的删除操作就会超过 400ms 下的 $4\times {10}^7$ 次运算量，且不包括 I/O 开销。

正确的做法可以用空间换时间，用一个 ${10}^5+10$ 的 vector 来存模拟静态链表，因为 vector 的随机访问只需要 $O(1)$。利用题目给的 head 结点一层一层的查找出链表，存储它的节点信息，然后按权重对链表节点进行排序。这时候无需特意存储 next 信息，只需要按照权重和地址先后顺序排序即可。 这里每一步操作都是 $O(1)$，自然不用担心超时风险了。

bool cmp(SortNode a, SortNode b)
{
    return a.rank != b.rank ? a.rank < b.rank : a.position < b.position;
}

当然，选择 map 还是数组模拟主要取决于题目规模，规模较小的用数组模拟可以减少时间，而大规模为避免 MLE 需要选择 map 离散化，例如下面这题。

牛客周赛 Round 31 D

D-小红数组操作_牛客周赛 Round 31 (nowcoder.com) 可以使用 map 模拟一个静态链表，用数组 r，l 表示每个节点的左右节点。这里 map 的键又是地址又是值。 初始化

int op = -1e9-1, ed = 1e9+1;
//初始化链表，只两个头尾节点
r[op] = ed, l[ed] = op;

插入 插入操作就是插入一个新节点在 ll 和 rr 结点中间，改变这三个结点的左右地址。

int x = 114514;
ll = a, rr = b;//将b插入到a的右侧,值为x
r[ll] = x;
l[rr] = x;
l[x] = ll;
r[x] = rr;

删除 相反操作，方便起见不用回收那个删除的节点。

int x = 114514;
ll = l[x], rr = r[x];
l[rr] = ll;
r[ll] = rr;

适用于 PTA 的链表模拟思路

挑出节点的时候记录链表的地址即可，每次访问则从静态链表中读取。前后地址的输出只要从挑出的地址中选择前后项即可，至于最后一项则为-1。 https://blog.csdn.net/liuchuo/article/details/126209963