[已解决]一道洛谷入门题 不知道哪里错了

FlyingEgg

题目
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

例如 输入                                 输出
                4
                4 3 2 1                            6




i]我的代码[/i]

#include<stdio.h>
#include<iostream>
using namespace std;
int main ()
{
        int i,n,sum,j,t;
       
                cin>>n;
                int A[n];
                for(i=0;i<n;i++)                                  //输入n
            {
                cin>>A[i];
                }


       
        for(i=0;i<n-1;i++)                                  //大循环 记录要跑多少轮  例如n=4  就要跑三轮
        {
                for(j=0;j<n;j++)                               //小循环  每个相邻的数挨个检测  
                {
                        if(A[j]>A[j+1])
                        {
                           t=A[j];                                 //翻转
                           A[j]=A[j+1];
                           A[j+1]=t;
                               
                                sum=sum+1;                            //记录翻转次数
                        }
                }
               
               
        }
       
    cout<<sum<<endl;
       
        return 0;
}

最佳答案

月排行榜 / 总排行榜

ba21

2022-3-14 19:39:33

冒泡，你的代码有问题。

1. #include<stdio.h>
   
2. #include<iostream>
   
3. using namespace std;
   
4. int main ()
   
5. {
   
6.     int i,n,sum=0,j; // sum 初始化
   
7. 
   
8.     cin>>n;
   
9.     int A[n];
   
10. 
    
11.     for(i=0; i<n; i++)
    
12.     {
    
13.         cin>>A[i]; // A[i]
    
14.     }
    
15. 
    
16. 
    
17. 
    
18.     for(i=0; i<n-1; i++)
    
19.     {
    
20.         for(j=0; j<n; j++)
    
21.         {
    
22.             if(A[j]>A[j+1])
    
23.             {
    
24.                 A[j]^=A[j+1]; // 使用异或 可不用中间变量
    
25.                 A[j+1]^=A[j];
    
26.                 A[j]^=A[j+1];
    
27. 
    
28.                 sum=sum+1;
    
29.             }
    
30.         }
    
31. 
    
32.     }
    
33.    
    
34.     for(i=0; i<n; i++)
    
35.     {
    
36.         cout << A[i] << ' ';
    
37.     }
    
38.     cout << endl;
    
39. 
    
40.     cout << sum << endl;
    
41. 
    
42.     return 0;
    
43. }
    

复制代码

跳转到最佳答案楼层

傻眼貓咪

泡沫排序法

二米阳光

冒泡算法可以解决这个问题

ba21

冒泡，你的代码有问题。

1. #include<stdio.h>
   
2. #include<iostream>
   
3. using namespace std;
   
4. int main ()
   
5. {
   
6.     int i,n,sum=0,j; // sum 初始化
   
7. 
   
8.     cin>>n;
   
9.     int A[n];
   
10. 
    
11.     for(i=0; i<n; i++)
    
12.     {
    
13.         cin>>A[i]; // A[i]
    
14.     }
    
15. 
    
16. 
    
17. 
    
18.     for(i=0; i<n-1; i++)
    
19.     {
    
20.         for(j=0; j<n; j++)
    
21.         {
    
22.             if(A[j]>A[j+1])
    
23.             {
    
24.                 A[j]^=A[j+1]; // 使用异或 可不用中间变量
    
25.                 A[j+1]^=A[j];
    
26.                 A[j]^=A[j+1];
    
27. 
    
28.                 sum=sum+1;
    
29.             }
    
30.         }
    
31. 
    
32.     }
    
33.    
    
34.     for(i=0; i<n; i++)
    
35.     {
    
36.         cout << A[i] << ' ';
    
37.     }
    
38.     cout << endl;
    
39. 
    
40.     cout << sum << endl;
    
41. 
    
42.     return 0;
    
43. }
    

复制代码

FlyingEgg

ba21 发表于 2022-3-14 19:39
冒泡，你的代码有问题。

为什么用中间变量就不行了呢   我发现两个代码主要就差在那个部分  谢谢你！！

FlyingEgg

ba21 发表于 2022-3-14 19:39
冒泡，你的代码有问题。

懂了懂了  谢谢大牛！！

ba21

FlyingEgg 发表于 2022-3-14 20:38
为什么用中间变量就不行了呢   我发现两个代码主要就差在那个部分  谢谢你！！

没说你中间变量不行。哪个位置用异或交换更好