蓝桥杯 算法训练 自行车停放

蓝桥杯 算法训练 自行车停放

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

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

输入格式

　　第一行一个整数n。
　　第二行一个整数x。表示第一辆自行车的编号。
　　以下n-1行，每行3个整数x,y,z。
　　z=0时，表示编号为x的自行车恰停放在编号为y的自行车的左边
　　z=1时，表示编号为x的自行车恰停放在编号为y的自行车的右边

输出格式

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

样例输入

4
3
1 3 1
2 1 0
5 2 1

样例输出

3 2 5 1

数据规模和约定

　　n<=100000
　　自行车编号为不超过100000的正整数。

直接用链表怕超过时限，所以就用了结构体数组模拟双向链表

#include<iostream>
//#include<bits/stdc++.h>using namespace std;struct bike{bike *l;bike *r;
};int main()
{bike lst[100001];//数组模拟双向链表int n;//自行车总数int x;//第一个停进来的自行车cin>>n;cin >> x;bike *head=&lst[x];//放在最左边的自行车for (int i = 1; i < n;i++){int x, y, z;cin >> x >> y >> z;if(z)//编号为x的自行车停在y的右侧{if(lst[y].r!=NULL)//如果编号为y的自行车右边还有自行车{    lst[y].r->l = &lst[x];//y右边第一辆自行车的左边应该是新放进来的自行车lst[x].r = lst[y].r;//新放进来的自行车的右边应该是原来在y右边的自行车}lst[x].l = &lst[y];//相互连接lst[y].r = &lst[x];}else//停在左侧{if(lst[y].l!=NULL)//和上面if里面的一个意思{    lst[y].l->r = &lst[x];lst[x].l = lst[y].l;}lst[x].r = &lst[y];lst[y].l = &lst[x];if(&lst[y]==head)//新停的自行车在最左边{head = &lst[x];}}}for (int i = 0; i < n;i++){cout << head - lst << " ";head = head->r;}system("pause");return 0;
}