蓝桥杯练习系统（算法训练）ALGO-966 自行车停放

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　有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的正整数。

vector数组实现

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,x;
vector<int> L;
int main(){
	cin>>n>>x;
	L.push_back(x);
	vector<int>::iterator it;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		it=find(L.begin(),L.end(),y);
		if(z==0){
			L.insert(it,1,x);
		}else if(z==1){
			L.insert(it+1,1,x);
		}
	}
	for(int i=0;i<L.size();i++){
		cout<<L[i]<<" ";
	}
	return 0;
} 

 链表实现（但是运行超时）

#include<iostream>
using namespace std;
 
typedef struct node{
	int data;
	struct node *next;
}node,*linklist;
//找到 y结点 
node *find(linklist L,int y){
	node *p=L->next;
	while(p->data!=y&&p){
		p=p->next;
	}
	return p;
} 
int main(){
	linklist L=new node;
	L->next=NULL;
	int n;
	cin>>n;
	int x;
	cin>>x;
	node *s=new node;
	s->data=x;
	s->next=NULL;
	L->next=s;
	int cnt=n-1;
	while(cnt--){
		int x,y,z;
		cin>>x>>y>>z;
		if(z==0){//在左边 
			node *p=find(L,y);
			//先后插，再交换数据域
			node *s=new node;
			s->data=x;
			s->next=p->next;
			p->next=s;
			int t;
			t=s->data;
			s->data=p->data;
			p->data=t; 
		}else if(z==1){//x在y的右边 
			node *p=find(L,y);
			//后插
			node *s=new node;
			s->data=x;
			s->next=p->next;
			p->next=s;
		}
	} 
	node *p=L->next;
	while(p){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
	return 0;
}