自行车停放算法详解

图标

豆瓜

豆瓜网

豆瓜网专栏

首发
豆瓜 图标 2021-01-13 11:40:15

问题描述

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

代码超时 80

原因主要是在n非常大的情况下,在遍历整个可变长数组的过程中很费时

复制代码

1 #include<iostream>

2 #include<vector>

3 //anthor:ZQ

4 using namespace std;

5 int main(){

6     vector<int>obj;

7     vector<int>::iterator it;

8     int n,ns,nq,flag,n1;

9     cin>>n;

10     cin>>n1;

11     obj.push_back(n1);

12     for(int i=1;i<n;i++){

13         cin>>ns>>nq>>flag;

14         for(it=obj.begin();it!=obj.end();it++){

15             if(*it==nq){

16                 if(flag==0){

17                     obj.insert(it,ns);

18                 }else{

19                     obj.insert(it+1,ns);

20                 }

21                 break;

22             }

23         }

24     }

25     for(it=obj.begin();it!=obj.end();it++){

26         cout<<*it<<" ";

27     }

28     return 0;

29 }

复制代码

改进代码

不用去一个一个去寻找自行车位置,调用<algorithm>库中的函数find()直接锁定位置

代码:

复制代码

1 #include<iostream>

2 #include<vector>

3 #include<algorithm>

4 //anthor:ZQ

5 using namespace std;

6 int main(){

7     vector<int>obj;

8     vector<int>::iterator it;

9     vector<int>::iterator position;

10     int n,ns,nq,flag,n1;

11     cin>>n;

12     cin>>n1;

13     obj.push_back(n1);

14     for(int i=1;i<n;i++){

15         cin>>ns>>nq>>flag;

16         position=find(obj.begin(),obj.end(),nq);

17         if(flag==0){

18             obj.insert(position,ns);

19         }else{

20             obj.insert(position+1,ns);

21         }

22     }

23 //        for(it=obj.begin();it!=obj.end();it++){

24 //            if(*it==nq){

25 //                if(flag==0){

26 //                    obj.insert(it,ns);

27 //                }else{

28 //                    obj.insert(it+1,ns);

29 //                }

30 //                break;

31 //            }

32 //        }

33     for(it=obj.begin();it!=obj.end();it++){

34         cout<<*it<<" ";

35     }

36     return 0;

37 }


本文由豆瓜网专栏作家 豆瓜 投稿发布,并经过豆瓜网编辑审核。

转载此文章须经作者同意,并附上出处(豆瓜网)及本页链接。

若稿件文字、图片、视频等内容侵犯了您的权益,请联系本站进行 投诉处理

相关搜索

自行车停放
图标 图标

豆瓜

豆瓜网

豆瓜网专栏

  • 自行车停放算法详解

    图标
    豆瓜 图标 · 今天 11:40:15 · 0浏览
  • 网购移动硬盘有什么缺点

    图标
    豆瓜 图标 · 今天 11:39:18 · 4浏览
  • 分析怎么改ppt母版教程方法

    图标
    豆瓜 图标 · 今天 11:38:25 · 6浏览
  • 全部评论

    豆瓜

    豆瓜网

    豆瓜网专栏

  • 自行车停放算法详解
  • 网购移动硬盘有什么缺点
  • 分析怎么改ppt母版教程方法
  • 网页前端模板实现原理分析
  • 头条搜索广告投放介绍说明
  • 我来说两句