算法训练 自行车停放

解决遍历的超时问题 资源限制 时间限制：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的正整数。   代码超时 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 } 

 

 

原文链接:https://www.cnblogs.com/zq-dmhy/p/12372134.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有