基本情况
ABC 秒了,D 数组在空间复杂度上面第一次疯狂吃亏,吃了两次罚时过。
赛后看官方题解,发现C做法薄纱我。
C - Lining Up 2
这题一眼链表,我用双向链表实现,代码石山。
官方题解就题论题,更本质。
其实这题并没必要开双向链表,因为实际上只有一种位置关系,左到右。
直接维护一个类似单链表的数据结构就行了。
#include <iostream>
#include <vector>
int main() {
using namespace std;
unsigned N;
cin >> N;
vector<unsigned> B(N + 1, N + 1); // B[i] 存储下标对应的人的右边的人
unsigned front;// 队头
for(unsigned i = 1; i <= N; ++i){
int A;
cin >> A;
if(A < 0)
front = i;//维护队头
else
B[A] = i; //更新A右边的人
}
while(front <= N){ // 就类似邻接表遍历,从队头开始
cout << front << " ";
front = B[front];
}
cout << endl;
return 0;
}
标签:AtCoder,Beginner,Contest,题解,337,unsigned,链表,front
From: https://www.cnblogs.com/kdlyh/p/17978232