欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

信息学奥赛一本通——冒泡算法——1310:【例2.2】车厢重组

程序员文章站 2022-07-14 09:37:56
...

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

【输入】
有两行数据,第一行是车厢总数N(不大于10000),第二行是N个不同的数表示初始的车厢顺序。

【输出】
一个数据,是最少的旋转次数。

【输入样例】
4
4 3 2 1
【输出样例】
6


今天我们来看一下一道基础算法题,冒泡排序。
首先分析一下题目。有一座可以转动的桥,一次只能将相邻的两个车厢交换,问我们最少多少次将车厢号按从小到大排序。
而我们所用的算法就是:冒泡排序
冒泡算法:
比较相邻的前后两个数据,如果前面数据大于后面的数据,就将两个数据交换。
对数组的第1个数据到n个数据进行一次遍历后,最大的一个数据就“冒”到数组第n个位置
然后进行第二轮,第三轮,。。。

首先我们先来模拟一下样例。
信息学奥赛一本通——冒泡算法——1310:【例2.2】车厢重组
我们从头进行判断,比较第一个数和第二个数,发现前面的数大于后面的数,我们将它们的位置进行交换,
接着再把交换好的第二个数和第三个数比较,发现第二个数比第三个数大,所以我们把它们交换。
直到最后,我们将数字4依次和后面的所有数进行比较,如果4大于后面的数,我们把它们进行交换,
如果小于或等于则把4固定到这个位置,并从下一个位置的数开始比较。

这样每一次的排序,总能把当前数中的最大值给拍到最后。

这就要求我们在写代码的时候注意:
第一次循环,进行n-1次操作(最多进行n-1次排序,就可以把最大的数放到后面排好序了)
第二次循环,进行n-2次操作,(最多进行n-2次排序,就可以把第二大的数放到倒第二的位置了)
然后一次减小操作次数

因此,我们需要两重循环,第一重控制每一次的比较次数,第二重控制当前数和下一个数比较,并一直比较到结尾

下面话不多说,把代码奉上:

#include <iostream>

using namespace std;

const int N = 10010;

int n;
int a[N];//全局变量,默认a数组里的所有数的值都是0

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];//读入数据
    
    int cnt = 0;//计数
    for (int i = n - 1; i >= 1; i -- ){//控制每次循环的次数
        for (int j = 1; j <= i; j ++ ){//每次循环i次
            if (a[j] > a[j + 1]){//判断
                int temp = a[j];//交换两个数
                a[j] = a[j + 1];
                a[j + 1] = temp;
                cnt ++;
            }
        }
    }
    
    cout << cnt << endl;//输出结果
    
    return 0;
}
相关标签: 信息学奥赛