蓝桥杯练习013

试题 算法训练 自行车停放

资源限制

时间限制：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的正整数。

解题思路

//分析题目得出本题是链表的使用，可以用链表实现
//用c++库中的vector实现
//处理数据的读入
//1.先将第一辆自行车的编号push_back到vector中
//2、然后循环读取以下的n-1行数据，x，y，z分别是题目中要求的x，y，z。
//3.利用迭代器pos、find函数获取到y的位置，存储到pos中
//4.对z的值进行判断，z==0，在y的位置插入x，此时x在y的左边，否则在y的后边相邻的下一个位置插入x，此时x在y的右边
//5.最后用迭代器对vector中的数据进行输出即可

示例代码

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> v;
vector<int>::iterator pos;
int main()
{
    
  int n,x;//n为自行车的数量，x为第一辆自行车的编号
  cin>>n>>x;
  v.push_back(x);//将第一辆汽车编号存入到数组中

  for(int i=1;i<n;i++){
    
    int x,y,z;
    cin>>x>>y>>z;
    pos=find(v.begin(),v.end(),y);
    if(z==0)
      v.insert(pos,x);
    else
      v.insert(pos+1,x);
  }
  for(vector<int>::iterator it=v.begin();it!=v.end();it++)
    cout<<*it<<" ";
  cout<<endl;
  return 0;
}

队列操作

问题描述

队列操作题。根据输入的操作命令，操作队列（1）入队、（2）出队并输出、（3）计算队中元素个数并输出。

输入格式

第一行一个数字N。
　　下面N行，每行第一个数字为操作命令（1）入队、（2）出队并输出、（3）计算队中元素个数并输出。

输出格式

若干行每行显示一个2或3命令的输出结果。注意：2.出队命令可能会出现空队出队（下溢），请输出“no”，并退出。

解题思路

//利用STL中的queue解决该问题
//1.处理数据的读入
//2.在读入时进行判断操作
//3.对不同的输入进行不同操作

代码

#include<iostream>
#include<queue>
using namespace std;
queue<int> q;
int main()
{
    
	int N;
	cin>>N;
	int cmd;//命令
	int data;//数据
	for(int i=0;i<N;i++){
    
		cin>>cmd;
		if(cmd==1){
    //入队列命令
			cin>>data;
			q.push(data);//入队
		}else if(cmd==2){
    //出队列命令
			if(q.size()==0){
    //检测是否为空队列
				cout<<"no"<<endl;
				break;
			}
			cout<<q.front()<<endl;//输出队头元素
			q.pop();
		}else cout<<q.size()<<endl;//输出队列元素个数
	}
	return 0;
}