试题 算法训练 自行车停放

问题描述

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

总结：

一开始想的是数组，每次输入就遍历然后插入

但是最后那个测试点超时了

然后用vector来，直接找到要插入的点的位置，然后插入

最后输出的时候，一开始用的遍历器去输出，最后超时了

然后改用int来遍历，才极限通过

刚好CPU限时1s