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

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

冒泡，你的代码有问题。

#include<stdio.h>
#include<iostream>
using namespace std;
int main ()
{
    int i,n,sum=0,j; // sum 初始化

    cin>>n;
    int A[n];

    for(i=0; i<n; i++)
    {
        cin>>A[i]; // A[i]
    }



    for(i=0; i<n-1; i++)
    {
        for(j=0; j<n; j++)
        {
            if(A[j]>A[j+1])
            {
                A[j]^=A[j+1]; // 使用异或 可不用中间变量
                A[j+1]^=A[j];
                A[j]^=A[j+1];

                sum=sum+1;
            }
        }

    }
    
    for(i=0; i<n; i++)
    {
        cout << A[i] << ' ';
    }
    cout << endl;

    cout << sum << endl;

    return 0;
}

跳转到最佳答案楼层

傻眼貓咪

泡沫排序法

二米阳光

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

ba21

冒泡，你的代码有问题。

#include<stdio.h>
#include<iostream>
using namespace std;
int main ()
{
    int i,n,sum=0,j; // sum 初始化

    cin>>n;
    int A[n];

    for(i=0; i<n; i++)
    {
        cin>>A[i]; // A[i]
    }



    for(i=0; i<n-1; i++)
    {
        for(j=0; j<n; j++)
        {
            if(A[j]>A[j+1])
            {
                A[j]^=A[j+1]; // 使用异或 可不用中间变量
                A[j+1]^=A[j];
                A[j]^=A[j+1];

                sum=sum+1;
            }
        }

    }
    
    for(i=0; i<n; i++)
    {
        cout << A[i] << ' ';
    }
    cout << endl;

    cout << sum << endl;

    return 0;
}

FlyingEgg

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

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

FlyingEgg

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

懂了懂了  谢谢大牛！！

ba21

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

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