题目

题目描述

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

输入描述

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

输出描述

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

输入输出样例

示例

输入

输出

3 2 5 1

运行限制

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

解题

源码

C++

#include <iostream>
#include <list>
using namespace std;
int num, first, x, y, z;
list<int>::iterator loc[100003]; //使用编号作为数组地需要，在相应的数组中存入结点的位置！高啊！

int main()
{
	list<int> L;  //链表
	cin >> num >> first;
	L.push_back(first); //把第一辆车放到链表里
	loc[first] = L.begin();	  //把第一辆车的位置，存到以车编号为序号的数字里
	list<int>::iterator temp; //遍历用的迭代器
	for (int i = 1; i < num; i++)
	{
		cin >> x >> y >> z;
		temp = loc[y]; //将这个y需要的车的位置拿出来给了temp
		if (z > 0)  //放右边的时候
		{
			L.insert(++temp, x);  //放到temp后一个位置的前一个，也就是temp后面
			loc[x] = --temp;  //把刚放入的车子位置以车编号为数组下标存入数组
		}
		else
		{
			L.insert(temp, x);  //同理
			loc[x] = --temp;
		}
	}
	for (temp = L.begin(); temp != L.end(); temp++) //遍历序列输出
		cout << *temp << " ";
	return 0;
}

Python

n=int(input())
res=[input()]
for i in range(n-1):
  x,y,z=input().split()
  if z=='0':
    res.insert(res.index(y),x)
  else:
    res.insert(res.index(y)+1,x)
print(' '.join(res))

总结

C++版

有一个小技巧是利用数组记录每一辆车子的位置，这样可以直接定位到车子的位置，极大地减少了需要的时间。
用了STL容器，太舒服了，比直接写方便多。

//list容器的使用
#include<iostream>

//end()指向末尾的下一个元素

int main(){
    //定义链表
    list<int>node;

    //初始化链表，包含n个结点的链表
    for(int i=1;i<=n;i++)
        node.push_back(i);

    //遍历链表，用it遍历链表
    list<int>::iterator it = node.begin();
    while(node.size()>1){
        it++;

        //结束时回到首位置
        if(it == node.end())
            it = node begin();
    }

    list<int>::iterator next = ++it;
    //结束时回到头部
    if(next == node.end())
        next = node.begin();
    node.erase(--it);
    //删除这个结点
    it = next;
    //加载到下一个结点
}

Python版

RNM这个简单太多了，因为python可以自动转换数据结构，所以只用注意流程就行了==、