[自行车停放]

本文主要是介绍[自行车停放]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

有 nn 辆自行车依次来到停车棚，除了第一辆自行车外，每辆自行车都会恰好停放在已经在停车棚里的某辆自行车的左边或右边。(e.g.停车棚里已经有 33 辆自行车，从左到右编号为：3,5,13,5,1。现在编号为 22 的第 44 辆自行车要停在 55 号自行车的左边，所以现在停车棚里的自行车编号是：3,2,5,13,2,5,1)。给定nn辆自行车的停放情况，按顺序输出最后停车棚里的自行车编号。n\leq 100000n≤100000。

输入描述
第一行一个整数 nn。 第二行一个整数xx。表示第一辆自行车的编号。 以下 n-1n−1 行，每行 33 个整数 x,y,zx,y,z。 z=0z=0 时，表示编号为 xx 的自行车恰停放在编号为 yy 的自行车的左边。 z=1z=1 时，表示编号为 xx 的自行车恰停放在编号为 yy 的自行车的右边。

输出描述
从左到右输出停车棚里的自行车编号

示例
输入

4
3
1 3 1
2 1 0
5 2 1

输出

3 2 5 1

运行限制
最大运行时间：1s
最大运行内存: 128M

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
struct node{                          //双向链表
    //int id;                         //结点编号，没用到
    int data;                         //数据
    int preid;                        //前一个结点
    int nextid;                       //后一个结点
}nodes[N];
int now;
int locate[N];    //locate(x) = now; 值为x的结点位置在nodes[now]
void init() {
    nodes[0].nextid = 1;
    nodes[1].preid  = 0;
    now = 2;
}
void insert(int k, int x) {  //插入一个nodes[now]，插到nodes[k]的右面
    nodes[now].data = x;
    locate[x] = now;         //记录值为x的结点的位置
    nodes[now].nextid = nodes[k].nextid;
    nodes[now].preid = k;
    nodes[nodes[k].nextid].preid = now;
    nodes[k].nextid = now;
    now++;
}
int main() {
    int n;     cin >> n;
    init();
    int a;     cin >> a;    //第一辆车编号
    insert(0, a);
    n--;
    while (n--) {
        int x, y, z;   cin >> x >> y >> z;
        if (z == 0)    //把x插到y的左边
            insert(nodes[locate[y]].preid, x); //用locate[]快速定位
        else           //把x插到y的右边
            insert(locate[y], x);
    }
    for (int i = nodes[0].nextid; i != 1; i = nodes[i].nextid)
        cout << nodes[i].data << " ";

    return 0;
}

这篇关于[自行车停放]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！